При четных просмотрах четные позиции сравниваются с соседними нечетными. Обмены выполняются тогда, когда надо, чтобы больший из пары занял нечетную позицию. Таким образом, ключи с большими значениями перемещаются на дно списка. При этом должно быть столько просмотров, сколько необходимо для того чтобы переместить в позицию число, наиболее удаленное от своей конечной позиции. Затем выполняется заключительный просмотр, необходимый для того, чтобы опознать упорядоченность. В течение этого просмотра счетчик обменов равен 0. Данный метод требует, по крайней мере, двух просмотров – одного нечетного и одного четного.
Метод стандартного обмена (также называемый «методом пузырька») перемещает один элемент списка в соответствующую позицию при каждом просмотре. Таким образом, при первом просмотре запись с наибольшим ключом помещается в последнюю позицию, при втором просмотре запись со следующим по величине ключом перемещается в предпоследнюю позицию и т.д. Метод может быть преобразован так, что будет размещать элементы по убыванию.
При первом просмотре первый элемент списка сравнивается со своим непосредственным преемником, и, если этот преемник меньше, они меняются местами. Теперь больший элемент, расположенный во второй позиции, сравнивается с элементом из третьей позиции. Обмен происходит, если необходимо больший из них разместить в третьей позиции. Затем позиция 3 сравнивается с позицией 4, позиция 4 с позицией 5 и т.д. когда позиция N – 1 сравнивается с позицией N, просмотр заканчивается.
Если в списке элемент k – 1 расположен раньше чем k, то при каждом сравнении (k – 1): k больший элемент попадает в позицию k. Элемент, перемещаемый вниз, считается в данный момент наибольшим в списке. Когда при сравнении обнаруживается, что k-й элемент больше, обмен не происходит. Следовательно, каждый раз сравниваются элемент, считающийся наибольшим (k – 1), и его непосредственный преемник k.
Второй просмотр идентичен первому с той лишь разницей, что уже установленная позиция исключается из последовательности. Каждый последующий просмотр исключает очередную установленную позицию, укорачивая список.
Подсчет обменов ведется для каждого просмотра. Просмотр, в результате которого число обменов не увеличилось, заканчивает сортировку.
алгSort (арг целN, цел табA [1:N])
нач цел k, i, w
нц дляkотNдо N– 1
нц для iот 1 до N– k
еслиA[i] > A [i + 1]
тоw:= A[i]
A[i]:= A [i + 1]
A [i + 1]:= w
все
кц
кц
кон
При сортировке «методом пузырька» выполняется N – 1 просмотр, причем на i – м просмотре производится N – i сравнений. Общее количесво сравнений C = N× (N– 1)/2, то есть имеет порядок O(N2).
Метод просеивания (также называемый «линейной вставкой с обменом» или «челночной сортировкой») является самым лучшим из этих методов. Он отличается от других методов обмена тем, что не сохраняет фиксированной последовательности сравнений. Кроме этого, исчезает разделение на отдельные просмотры как следствие схемы последовательностей сравнений. Метод просеивания работает точно так же, как стандартный обмен до тех пор, пока не надо выполнять перестановку. Сравниваемая величина с меньшим ключом поднимается насколько это возможно вверх по списку. Она сравнивается «в обратном порядке» со всеми ее линейными предшественниками по направлению к вершине списка. Если ее ключ меньше, чем у предшественника, то выполняется обмен и начинается очередное сравнение. Когда элемент, передвигаемый вверх, встречается с меньшим ключом, этот процесс прекращается и нисходящие сравнения возобновляются с той позиции, с которой выполнялся первый обмен.
Будем называть нисходящее сравнение первичным, а восходящее вторичным. Любое первичное сравнение может увеличить число вторичных сравнений. Если первичное сравнение охватывает позиции 6 и 7, то цепочка вторичных сравнений может иметь самое большее 5 сравнений. Этот максимум достигается, если исходный ключ из позиции 7 меньше всех ключей в списке, расположенных выше этой позиции. Фактическая длина последовательности вторичных сравнений зависит от величины двигающегося вверх элемента относительно величины каждого элемента из предшествующей упорядоченной части списка.
Сортировка заканчивается, когда первичное сравнение охватит (N + 1) – й элемент.
Сортировка вставками
Сортировка вставками есть общее название группы методов сортировки, основанных на последовательной вставке «новых» элементов в увеличивающийся упорядочиваемый список. Среди них есть три существенно разных метода: линейная вставка, центрированная вставка и двоичная вставка. Эти методы сортировки различаются методами поиска подходящего места для вставки элемента. Простейшим методом является линейная вставка. Как следует из названия, в этом методе уже существующий список рассматривается как простой линейный список, просматриваемый поэлементно сверху вниз, пока не будет найдена соответствующая позиция для нового элемента.
Этот метод обычно используется тогда, когда процесс, внешний к данной сортировке, динамически вносит добавление в список, все элементы которого известны и который должен все время поддерживаться в упорядоченном состоянии. Сортировка выполняется каждый раз при получении нового элемента, размещая этот элемент в нужное место списка и облегчая контроль. Некоторые характеристики систем реального времени делают вставку полезным техническим приемом.
Связь между процессом, порождающим подлежащие сортировке числа, и сортировкой такова, что сортировка привлекается многократно. Такое повторное привлечение может быть сопряжено с некоторыми издержками, такими как передача параметров, вход и выход из процедуры. Эти издержки должны быть выявлены и учтены при анализе использования метода вставок таким способом. Сортировку вставками можно организовать как один унифицированный процесс.
Метод линейной вставки. Под сортировку выделяется количество памяти, равное предполагаемой длине окончательного списка из всех элементов. Счетчик длины списка в самом начале устанавливается равным нулю. При помощи этого счетчика контролируется длина области поиска нужной позиции для элемента, вставляемого в список. Сортировка привлекается для каждого элемента. Один «вызов» сортирующей подпрограммы размещает один элемент в списке и увеличивает счетчик списка на единицу.
Первый элемент помещается в верхнюю позицию области вывода. Следующий элемент, присоединяемый к списку, сравнивается с первым. Если ключ нового элемента больше, он помещается в позицию, следующую за позицией первого элемента. Если ключ нового элемента меньше, то первый элемент перемещается в позицию 2, а новый элемент помещается в позицию 1.
В дальнейшем все новые элементы последовательно сравниваются с каждым элементом списка, начиная с первого, до тех пор, пока не встретиться больший. Этот больший элемент и все последующие элементы списка передвигаются на одну позицию вниз. Таким образом освобождается место, на которое вставляется новый элемент.
Метод сортировки Шелла
Сортировка Шелла является расширением сортировки просеиванием. Последний просмотр в сортировке Шелла идентичен методу просеивания, описанному выше. Предшествующие просмотры используют тот же технический прием, но в них сравниваются и обмениваются не непосредственные соседи, а элементы отстоящие на заданное расстояние. Например, позиция 1 сравнивается с позицией 5, позиция 5 с позицией 9, 9 с 13 и т.д. Когда обнаружена инверсия, цепочка вторичных сравнений охватывает те элементы, которые входили в последовательность первичных сравнений. Например, если обнаружена инверсия между позициями 9 и 13, то возможная вторичная последовательность состоит из сравнений 5: 9 и 1: 5.
На каждом просмотре шаг между сравниваемыми элементами определяется путем сокращения вычисленного исходного шага. На последнем просмотре он сокращается до 1. Цель метода на ранних просмотрах – сократить число вторичных сравнений и обменов на более поздних просмотрах. В этом методе элементы могут совершать большие скачки к нужным позициям на ранних просмотрах, а не передвигаться на одну позицию за один раз. На последнем просмотре числа будут стремиться располагаться близко к своим позициям и, следовательно, потребуют незначительных перемещений при окончательном размещении.
Модификации метода различаются способами вычисления начального шага между элементами и правилами сокращения этого шага от просмотра к просмотру.
Вариант с отложенными обменами
При описании метода сортировки Шелла предполагалось, что обмен следует за каждым сравнением, которое выявляет элемент больший, чем предыдущий элемент части. В алгоритме (опубликованном Хиббардом) использован метод, сокращающий число обменов. Этот алгоритм отличается то ранее описанного тем, что он использует временную память для хранения сравниваемых элементов в течение всей последовательности сравнений.
Каждое первичное сравнение Ключi: ключi+шаг включает пересылку ключi+шаг во временную память. Сравнение позиции 1 с позицией 4, например, на самом деле включает пересылку из позиции 4 во временную память и сравнение ключа из временной памяти с ключом из позиции 1. Если ключiбольше, он перемещается в позицию ключi+шаг. Если ключi+шаг больше, то перемещение не нужно. Пересылка во временную память позволяет эффективно освобождать позицию последующего элемента этой части.