Алгоритмы сортировкиПод сортировкой понимается процесс перегруппировки элементов массива, приводящий к их упорядоченному расположению относительно ключа. Цель сортировки – облегчить последующий поиск элементов. Метод сортировки называется устойчивым, если в процессе перегруппировки относительное расположение элементов с равными ключами не изменяется. Основное условие при сортировке массивов – это не вводить дополнительных массивов, т.е. все перестановки элементов должны выполняться в исходном массиве. Сортировку массивов принято называть внутренней, а сортировку файлов – внешней. Методы внутренней сортировки классифицируются по времени их работы. Хорошей мерой эффективности может быть число операций сравнений ключей и число пересылок (перестановок) элементов. Прямые методы имеют небольшой код и просто программируются, быстрые, усложненные методы требуют меньшего числа действий, но эти действия обычно более сложные, чем в прямых методах, поэтому для достаточно малых значений 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 раз, чем метод Шелла.
|
