Элементарные методы сортировки (стр. 2 из 2)
Этот процесс реализован в следующей программе. Для каждого i от 2 до N, подмассив a [1..i] сортируется посредством помещения a[i] в подходящую позицию среди уже отсортированных элементов:
Также как и при сортировке выбором, в процессе сортировки элементы слева от указателя i находятся уже в сортированном порядке, но они не обязательно находятся в своей последней позиции, поскольку их еще могут передвинуть направо чтобы вставить более маленькие элементы встреченные позже. Массив становится полностью сортированным когда указатель достигает правого края.
Однако имеется еще одна важная деталь: программа insertion не всегда работает, поскольку while может проскочить за левый край массива, когда v – самый меньший элемент массива. Чтобы исправить ситуацию, мы помещаем «сторожевой» ключ в a[0], делая его, по крайней мере, не больше, чем самый маленький ключ массива. Сторожевые элементы повсеместно используются в ситуациях подобных этой для предотвращения дополнительной проверки (в данном случае j>0), что почти всегда помогает во внутренних циклах.
Пузырьковая сортировка
Элементарный метод сортировки, который часто дают на вводных занятиях – это пузырьковая сортировка: Стоящие рядом элементы массива обмениваются местами, до тех пор, пока встречаются неотсортированные пары. Реализацияэтогометодадананиже.
Чтобы поверить в то, что она на самом деле работает, может потребоваться некоторое время. Для этого заметьте, что когда во время первого прохода мы встречаем максимальный элемент, мы обмениваем его с каждым элементом справа от него пока он не окажется в крайней правой позиции. На втором проходе мы помещаем второй максимальный элемент в предпоследнюю позицию и так далее. Пузырьковая сортировка работает также как и сортировка выбором, хотя она и делает гораздо больше работы на то, чтобы переместить элемент в его конечную позицию.
Характеристики простейших сортировок
Свойство 1Сортировка выбором использует около 
сравнений и N обменов.
Свойство 2 Сортировка вставкой использует около 
сравнений и 
обменов в среднем, и в два раза больше в наихудшем случае.
Свойство 3Пузырьковая сортировка использует около сравнений и обменов в среднем и наихудшем случаях.
Свойство 4Сортировка вставкой линейна для «почти сортированных» файлов.
Свойство 5Сортировка выбором линейна для файлов с большими записями и маленькими ключами.
Сортировка файлов с большими записями
Очень часто бывает возможно (и желательно) сделать так, чтобы при сортировке файла состоящего из N элементов любом методом было бы сделано только N операций обмена полной записи посредством косвенной адресации к элементам массива (используя массив индексов или указателей), а саму реорганизацию делать после.
Более конкретно: если массив a [1..N] содержит большие записи, то мы предпочтем использовать массив указателей p [1..N] для того, чтобы знать, где находится очередной элемент массива a, и для произведения псевдообмена. Нижеприведенапрограммасортировкивставкойсиспользованиеммассивауказателей:
Для предотвращения излишнего контроля в цикле, в программе опять используются «сторожевые» элементы.
Изначально, индексы идут по порядку. Потом порядок индексов начинает меняться так, чтобы массив a, прочитанный по порядку чтения индексов был упорядочен.
Для этого мы можем использовать следующую процедуру, которая физически упорядочивает записи файла используя при этом N перестановок:
Сортировка Шелла
Сортировка вставкой работает медленно потому, что она обменивает только смежные элементы. Оболочечная сортировка является простейшим расширением сортировки вставкой, которая увеличивает скорость работы алгоритма за счет того, что позволяет обменивать элементы находящиеся далеко друг от друга.
Основная идея алгоритма состоит в том, чтобы отсортировать все группы файла состоящие из элементов файла отстоящих друг от друга на расстояние h. Такие файлы называются h-сортированными. Когда мы h-сортируем файл по некоторому большому h, мы передвигаем его элементы на большие растояния. Это облегчает работу сортировки для меньших значений h. Процесс заканчивается когда h уменьшается до 1.
Приведенная программа использует последовательность… 1093, 364, 121, 40, 13, 4, 1. Могут существовать и другие последовательности – одни лучше, другие хуже.
Свойство 6 Оболочечная сортировка никогда не делает более чем N1.5 сравнений для вышеуказанной последовательности h.
Подсчетраспределения
Во многих случаях мы знаем, что значения ключей в файле лежат в каких либо пределах. В этих ситуациях применим алгоритм, именуемый подсчет распределения. Здесьприведенапрограммадляэтогопростогоалгоритма.