Бинарные и двухпутевые вставки

 

Поиск ячеек между которыми следует вставить новую запись можно модифицировать, учитывая тот факт, что первоначальный массив уже отсортирован. Например, если вставляется 64-я запись, можно сначала сравнить ключ K₆₄ с K₃₂ а затем, если он меньше, сравнить его с К₁₆, а если больше - с К₄₈ и т. д. Данный метод называется методом бинарных вставок. Однако данный метод позволяет решить задачу только наполовину: после того как найдено место, куда следует вставлять запись R_j все равно необходимо осуществить сдвиг примерно j/2 ранее рассортированных записей, чтобы освободить место для R_j.

Таким образом, в обоих описанных методах самой продолжительной по времени является операция сдвига элементов в массиве. Метод двухпутевых вставок, впервые предложенный в начале 50-х годов прошлого века позволяет несколько сократить ее продолжительность. Иллюстрация метода представлена на рисунке 24. Здесь первый элемент помещается в середину области вывода и место для последующих элементов освобождается при помощи сдвигов влево или вправо, туда, куда удобнее. Таким образом удается сэкономить примерно половину времени работы по сравнению с использованием метода простых вставок за счет некоторого усложнения программы.

Рис. 24. Процесс сортировки методом двухпутевых вставок

Метод Шелла

 

Для алгоритмов сортировки, который каждый раз перемещает запись только на одну позицию, среднее время выполнения будет в лучшем случае пропорционально N², потому что в процессе сортировки каждая запись должна пройти в среднем через N/3 позиций. Поэтому, если желательно получить метод, существенно превосходящий по скорости метод простых вставок, необходим механизм, с помощью которого записи могли бы перемещаться сразу на несколько позиций.

Один из таких методов был предложен в 1959 году Дональдом Л. Шеллом и известен во всем мире под именем своего автора. На рис. 25 проиллюстрирована общая идея, которая лежит в его основе для массива из 16 записей. Сначала они делятся на 8 групп по две записи в каждой: (R₁,R₉), (R₂,R₁₀), … , (R₈, R₁₆). Каждая из этих групп сортируется по возрастанию. В результате сортировки каждой группы записей по отдельности приходим ко второй строке рис. 25. Этот процесс называется первым проходом. Далее записи делятся на четыре группы по четыре в каждой: (R₁,R₅,R₉,R₁₃), (R₄, R₈,R₁₂,R₁₆). Затем опять сортируется каждая группа в отдельности. Результат этого второго прохода показан в третьей строке.

 

Рис. 25. Сортировка методом Шелла со смещениями 8, 4, 2, 1

 

На третьем проходе сортируются две группы по восемь записей; процесс завершается четвертым проходом, во время которого сортируются все 16 записей. В каждой из промежуточных стадий сортировки участвуют либо сравнительно короткие массивы, либо уже сравнительно хорошо упорядоченные массивы, поэтому на каждом этапе можно пользоваться методом простых вставок и сортировка выполняется довольно быстро.

Метод сортировки Шелла также известен под именем метода сортировки с "убывающим смещением", поскольку каждый проход характеризуется смещением h, таким, что сортируются записи, каждая из которых отстоит от предыдущей на h позиций. На практике можно пользоваться любой последовательностью h_t-1,h_t-2,…,h₀, но последнее смещение h₀ должно быть равно 1. Однако следует иметь в виду, что выбор значений смещений на последовательных проходах имеет весьма существенное значение для скорости сортировки.

Для задания значений h₀,h₁,… предлагается следующее правило.

Если N достаточно большое (больше 1000), то рекомендуется использовать последовательность Седгевика:

которая обрывается на h_t-1, если 3h_t>=N

Седгевик доказал, что когда используются сформированные по этому правилу смещения (h₀, h₁, h₂,…)=(1, 5, 19, …), то время выполнения в худшем случае не превышает O(N^4/3).

Обменная сортировка

 

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

Метод пузырька

 

Пожалуй, наиболее очевидный способ обменной сортировки заключается в том, чтобы сравнить К₁ с К₂, меняя местами R₁ и R₂, если их ключи расположены не в нужном порядке, и затем проделать то же самое с R₂ и R₃, R₃ и R₄ и т. д. При выполнении этой последовательности операций записи с большими ключами будут продвигаться вправо; и действительно, все это закончится тем, что запись с наибольшим ключом займет положение R_N При многократном выполнении данного процесса соответствующие записи попадут в позиции R_N-1, R_N-2 и т. д., так что, в конце концов, все записи будут упорядочены. Последовательность чисел удобно представлять не горизонтально, а вертикально, чтобы запись R_N была в самом верху, a R₁ - в самом низу. Метод назван "методом пузырька", потому что большие элементы, подобно пузырькам, "всплывают" на соответствующую позицию.

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

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

Однако несмотря на свою простоту, он поддается дальнейшему улучшению.

Первое улучшение алгоритма заключается в запоминании того, производился ли на данном проходе какой-либо обмен. Если нет - алгоритм заканчивает работу. Оптимизацию можно продолжить, если запоминать не только сам факт обмена, но и индекс последнего обмена k. Дальнейшие проходы можно заканчивать на индексе k, вместо того чтобы двигаться до установленной заранее верхней границы.

При сортировке методом пузырька можно менять направление следующих один за другим проходов. Получившийся алгоритм иногда называют "шейкер-сортировкой". На практике метод пузырька, даже с улучшениями, работает, увы, слишком медленно. А потому - почти не применяется.