Когда ключiбольше, чем ключi+шаг, то ключiпересылается из своей позиции в «свободную» позицию, и метод начинает последовательность вторичных сравнений. Содержимое временной памяти (ключi+шаг) – это запись, поднимающаяся на верх данной части. Ключ каждой записи сравнивается с временной памятью и, если обнаружено, что он больше, пересылается вниз списка в текущую свободную позицию. Каждая пересылка освобождает позицию перемещенного элемента. Когда в списке обнаружен элемент с ключом, меньшим ключа временной памяти, содержимое временной памяти помещается в позицию списка освобожденной самой последней, т.е. в нужное место.
Использование временной памяти эффективно тогда, когда длина последовательности вторичных сравнений не меньше 2. Поскольку, скорее всего это верно для списков произвольной конечной длины со случайно упорядоченными данными, то вариант с отложенными обменами может, вообще говоря, быть лучше других сортировок Шелла.
Быстрая сортировка
Метод быстрой сортировки был впервые описан Ч.А.Р. Хоаром В 1962 году. Быстрая сортировка – это общее название ряда алгоритмов, которые отражают различные подходы к получению критичного параметра, влияющего на производительность метода.
Метод быстрой сортировки. Некоторый элемент списка выбирается в качестве «основы». Все элементы, меньше основы, размещаются в позициях с начала списка»; все элементы, больше основы, размещаются в позициях с конца списка. Элементы сравниваются с основой и изменяют свою позицию, когда они больше и расположены в писке выше нее, или когда меньше и расположены в списке ниже нее. Это упорядочение составляет этап сортировки. В конце этапа для размещения основы пригодна некоторая позиция в списке. Эта позиция соответствует месту основы в окончательном списке, поскольку ее относительный адрес в списке определяется числом элементов выше и ниже нее.
Этап определяет две части. Если значение основы хорошо аппроксимирует медиану списка, то эти две части будут примерно равной длины. Если основа является наихудшей возможной оценкой медианы (наибольшим или наименьшим элементом списка), то эти части будут длиной 0 и К – 1, где К – это длина исходного списка.
Способ построения частей, по существу, один и тот же во всех версиях алгоритма. Устанавливаются два указателя, один на начало, другой на конец списка. После выбора основы поиск меньшей величины начинается с указателя конца, перемещающегося вверх к началу списка. Сравнения продолжаются до тех пор, пока не будет найден элемент, меньший основы, или не будет исчерпан список.
Когда элемент, меньшей основы, найден, его необходимо переместить в позицию, содержащий элемент, большей основы. Эта позиция находится при сравнениях, использующих указатель начала. Сравнения выполняются сверху в низ по списку до тех пор, пока указатель начала не укажет на больший элемент. Таким образом, элементы, больший и меньший основы, идентифицированы, и теперь выполняется обмен между ними.
Модификации возникают только в методе пересылки элементов данных. Один способ состоит в том, что основа пересылается во временную память, а содержимое начала списка перемещается в освободившуюся позицию. При этом освобождается начальная позиция, куда можно переместить элемент. После пересылки свободная позиция сдвигается в ячейку, расположенную близко к концу списка. При нисходящем поиске отыскивается элемент для пересылки в эту свободную позицию. Свободная позиция чередуется с верхней и нижней позициями до тех пор, пока указатели не совместятся.
После обмена или двойной пересылки возобновляется поиск другого элемента, меньшего основы. Когда он найден, начинается поиск большего элемента с использованием указателя начала. Этот процесс продолжается до тех пор, пока два указателя не встретятся. Относительная длина частей определяется позицией в списке, в которой совместятся указатели начала и конца. В некоторых версиях этого метода необходимо сравнивать относительные позиции указателей после каждого перемещения по списку вверх или вниз.
На первом этапе строятся две части. Одна из них используется в качестве исходной на втором этапе, вторая помещается в стек LIFO. Общее правило таково: первой обрабатывать меньшую часть, а границы большей запоминать в стеке. Второй этап порождает две части. Меньшая обрабатывается на третьем этапе, а большая перемещается в стек над большей частью, построенной на этапе 1. Процесс порождения частей, запоминания большей из них в стеке и разделения меньшей продолжается до тех пор, пока все части не сократятся до одного элемента. При возникновении одноэлементной части новая часть для стека не строится. Ожидающие части выбираются из стека и обрабатываются. Сортировка выполнена, когда стек пуст.
Обработка меньшей из двух частей гарантирует, что ожидающих частей в стеке будет не более log2N. Последовательность обработки частей совершенно произвольна и может изменяться по желанию программиста.
Быстрая сортировка может использоваться в комбинированном алгоритме, чтобы сократить части до заранее определенного размера, после чего они упорядочиваются другим методом, более эффективным для малых списков.
АлгQuickSort (аргцелm, t)
начцелi, j, x, w
i:= m
j:= t
x:= div (A (m + t), 2)
нц
нцпокаA[i] < x
i:=i+1
кц
нц пока A[j] > x
j:=j-1
кц
если i <= j
то
w:= A[i]
A[i]:= A[j]
A[j]:= w
i:= i+1
j:= j-1
все
кц пока i > j;
если m < j
то QuickSort (m, j);
все
еслиi < t
тоQuickSort (i, t);
все
кон
Оценим эффективность метода. Предположим, что размер массива равен числу, являющемуся степенью двойки, и при каждом разделении элемент X находится точно в середине массива. В этом случае при первом просмотре выполняется Nсравнений и массив разделяется на две части размерами »N/2 сравнений и т.д. следовательно,
C = N + 2 × (N / 2) + 4 × (N / 4) + … + N × (N / N) = O(N ×log2N).
Внутреннее слияние
Основой процесса слияния является фундаментальная идея упорядочения данных путем чередования элементов из двух или более упорядоченных списков. Упорядоченное объединение этих списков представляет собой окончательный упорядоченный список из десяти элементов. Сравниваются наименьшие элементы каждой части и меньшей из них продвигается в список вывода. Процесс сравнения элементов, продвижения меньшего в список вывода и выбор преемника в «победившей» части продолжается до тех пор, пока не исчерпывается одна из частей. После того как одна часть исчерпана, все оставшиеся элементы другой пересылаются в список вывода.
АлгSl (арг целk, m, q, цел табA [1:N])
начцелk, i, j, t, целтабA [1:N]
i:= k
j:= m+1
t:= 1
нц пока (i <= m) и (j <= q)
еслиA[i] <= A[j] то
D[t]:= A[i]
i:= i +1
иначе
D[t]:= A[j]
j:= j+1
t:= t +1
все
кц
нцпокаi = m
D[t]:= A[i]
i:= i +1
t:= t +1
нцпокаj:= q
D[t]:= A[j]
j:= j +1
t:= t +1
кц
кц
нц для iот 1 до t – 1
A [k+ i– 1]:= D[i]
кц
кон
Эффективность алгоритма составляет C = O (N×log2N).