Сортировка выбором

Алгоритмы сортировки. Метод пузырька

Общие понятия

Сортировка – это процесс упорядочения элементов массива или списка по возрастанию или убыванию.

Существует много алгоритмов сортировки, отличающихся по ряду характеристик:

· Время работы, или вычислительная сложность – количество операций, затрачиваемых алгоритмом. Обычно оценивается худший сценарий, когда исходный массив оказывается максимально неупорядочен с точки зрения алгоритма.

· Затрачиваемая память (помимо исходного массива) – некоторые алгоритмы требуют выделения дополнительной памяти для временного хранения данных или формирования нового выходного массива.

Кроме того, алгоритмы можно разделить по типу доступа к данным:

· Алгоритмы внутренней сортировки применяются для сортировки данных, целиком находящихся в оперативной памяти.

· Алгоритмы внешней сортировки оперируют данными, не помещающимися в оперативную память. Такие алгоритмы используют внешнюю память, доступ к которой требует существенно большего времени, поэтому требуются специальные алгоритмические решения, чтобы каждый элемент использовался алгоритмом минимальное количество раз.

Данный алгоритм является достаточно простым и поэтому получил широкое распространение. Вычислительная сложность алгоритма квадратичная – O(n²), поэтому алгоритм эффективен только на небольших массивах данных.

Алгоритм проходит все элементы массива и попарно сравнивает их друг с другом. Если порядок сравниваемых элементов неверный, алгоритм меняет элементы местами:

// Сортировка пузырьком

void BubbleSort(ref int[] Array)

{

// Перебираем элементы массива (без последнего)

for (int i = 0; i < Array.Length – 1; i++)

// Перебираем все элементы справа от i

for (int j = i + 1; j < Array.Length; j++)

// Правильный ли порядок элементов?

if (Array[i] > Array[j])

{

// Нет – меняем порядок

int t = Array[i];

Array[i] = Array[j];

Array[j] = t;

}

}

Сортировка выбором имеет квадратичную сложность O(n²) и, как и предыдущий метод пузырька, эффективен лишь на небольших объемах данных.

Алгоритм находит номер минимального значения в текущем списке, меняет этот элемент со значением первой неотсортированной позиции (если минимальный элемент не находится на данной позиции), а затем сортирует хвост списка, исключив из рассмотрения уже отсортированные элементы:

// Сортировка выбором

void SelectionSort(ref int[] Array)

{

// Перебираем все элементы массива (безпоследнего)

// i – позиция первого неотсортированного элемента

for (int i = 0; i < Array.Length – 1; i++)

{

// Позиция минимального элемента справа от i

int min = i;

// Перебираем все элементы справа от i

for (int j = i + 1; j < Array.Length; j++)

// Меньше ли очередной элемент минимального?

if (Array[j] < Array[min])

// Да – теперь это минимальный элемент

min = j;

// Минимальный элемент не первый?

// Меняем местами!

if (min!= i)

{

int t = Array[i];

Array[i] = Array[min];

Array[min] = t;

}

}

}

Дата добавления: 2014-11-07