Алгоритмы сортировки

Под сортировкой понимается процесс перегруппировки элементов массива, приводящий к их упорядоченному расположению относительно ключа.

Цель сортировки – облегчить последующий поиск элементов. Метод сортировки называется устойчивым, если в процессе перегруппировки относительное расположение элементов с равными ключами не изменяется. Основное условие при сортировке массивов – это не вводить дополнительных массивов, т.е. все перестановки элементов должны выполняться в исходном массиве. Сортировку массивов принято называть внутренней, а сортировку файлов – внешней.

Методы внутренней сортировки классифицируются по времени их работы. Хорошей мерой эффективности может быть число операций сравнений ключей и число пересылок (перестановок) элементов.

Прямые методы имеют небольшой код и просто программируются, быстрые, усложненные методы требуют меньшего числа действий, но эти действия обычно более сложные, чем в прямых методах, поэтому для достаточно малых значений n (n £ 50) прямые методы работают быстрее. Значительное преимущество быстрых методов начинает проявляться при n ³ 100.

Среди простых методов наиболее популярны следующие.

1. Метод прямого обмена (пузырьковая сортировка):

for (i = 0; i < n–1; i++)

for (j = i+1; j < n; j++)

if (a[i].key > a[j].key) { // Переставляем элементы

r = a[i];

a[i] = a[j];

a[j] = r;

}

2. Метод прямого выбора:

for (i = 0; i < n–1; i++) {

m = i;

for (j = i+1; j < n; j++)

if (a[j].key < a[m].key) m = j;

r = a[m]; // Переставляем элементы

a[m] = a[i];

a[i] = r;

}

Реже используются: 3) сортировка с помощью прямого (двоичного) включения; 4) шейкерная сортировка (модификация пузырьковой).

К улучшенным методам сортировки относятся следующие.

1. Метод Д. Шелла (1959), усовершенствование метода прямого включения.

2. Сортировка с помощью дерева, метод HeapSort, Д.Уильямсон (1964).

3. Сортировка с помощью разделения, метод QuickSort, Ч.Хоар (1962), улучшенная версия пузырьковой сортировки, являющийся на сегодняшний день самым эффективным методом.

Идея метода разделения QuickSort в следующем. Выбирается значение ключа среднего m -го элемента x = a [ m ]. key. Массив просматривается слева – направо до тех пор, пока не будет обнаружен элемент a [ i ]. key > x. Затем массив просматривается справа – налево, пока не будет обнаружен элемент a [ j ]. key < x. Элементы a [ i ] и a [ j ] меняются местами. Процесс просмотра и обмена продолжается до тех пор, пока i не станет больше j. В результате массив оказывается разбитым на левую часть a [ L ], 0 £ L £ j с ключами меньше (или равными) x и правую a [ R ], i £ R < n с ключами больше (или равными) x.

Алгоритм такого разделения очень прост и эффективен:

i = 0; j = n – 1; x = a[(L + R)/2].key;

while (i < = j) {

while (a[i].key < x) i++;

while (a[j].key > x) j--;

if (i < = j) {

r = a[i]; // Переставляем элементы

a[i] = a[j];

a[j] = r;

i++; j--;

}

}

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

Сравнение методов сортировок показывает, что при n > 100 наихудшим является метод пузырька, метод QuickSort в 2-3 раза лучше, чем HeapSort, и в 3-7 раз, чем метод Шелла.