Быстрые алгоритмы сортировки

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

Сортировка Шелла была предложена Дональдом Л.Шеллом в 1959 г. Метод пытается повысить скорость работы за счет быстрого перемещения элементов, находящихся далеко от нужных позиций. Сортировка предполагает перемещение таких элементов большими «прыжками», а окончательная установка в нужные позиции может быть выполнена одним из классических способов.

Качественный порядок сортировки остается O(n²), но среднее число сравнений, определенное эмпирическим путем – n·log₂n². Ускорение достигается за счет того, что выявленные «не на месте» элементы при шаге сравнения большем единицы быстрее «всплывают».

Следующий пример представляет реализацию сортировку Шелла, основанную на пузырьковом алгоритме. Исходный шаг сравнения h соизмерим с половиной общего размера последовательности. Сначала выполняется пузырьковая сортировка с интервалом h. Затем величина h уменьшается вдвое и вновь выполняется пузырьковая сортировка, далее h уменьшается еще вдвое и т.д. Последняя пузырьковая сортировка выполняется при h=1.

{ Сортировка Шелла }

procedure ShellSort(aList: TList; aCompare: TCompareFunc);

Var

h, i, t, N: Integer;

Temp: Pointer;

{ Признак перестановки }

k: Boolean;

Begin

N:=aList.Count;

{ Начальное значение интервала }

h:=N div 2;

{ Цикл с уменьшением интервала до 1 }

while h > 0 do

Begin

{ Пузырьковая сортировка с интервалом h }

k:=True;

{ Цикл, пока есть перестановки }

while k do

Begin

k:=False;

{ Сравнение элементов на интервале h }

for i:=0 to N-h-1 do

Begin

if aCompare(aList.List[i], aList.List[i+h]) = 1 then

Begin

{ Перестановка }

Temp:=aList.List[i];

aList.List[i]:=aList.List[i+h];

aList.List[i+h]:=Temp;

{ Признак перестановки }

k:=True;

end;

end;

end;

{ Уменьшение интервала }

h:=h div 2;

end;

end;

Результаты трассировки примера представлены в табл. 4.11.

Табл. 4.11. Трассировка сортировки Шелла.

В другой реализации сортировки установка элементов в нужные позиции выполняется методом вставок. Строго говоря, здесь метод Шелла работает путем вставки отсортированных подмножеств основного набора. Каждое подмножество формируется за счет выборки каждого h-ого элемента, начиная с любой позиций в наборе. В результате будет получено h подмножеств, которые отсортированы методом вставок.

Полученная последовательность называется отсортированной по h. Затем значение h уменьшается и вновь выполняется сортировка. Уменьшение h происходит до тех пор, пока h не будет равно 1, после чего последний проход будет представлять собой стандартную сортировку методом вставок (точнее сортировку по 1).

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

Выбор шага изменения играет важную роль. Шелл предложил в своей первой работе значения 1, 2, 4, 8, 16, 32 и т.д. Однако при таком наборе до последнего прохода элементы с четными индексами никогда не сравниваются с элементами с нечетными индексами. Следовательно, при выполнении последнего прохода все еще возможны перемещения элементов на большие расстояния (например, такая ситуация возможна, когда элементы с меньшими значениями находятся в позициях с четными индексами, а элементы с большими значениями – в позициях с нечетными индексами).

В 1969 г. Дональд Кнут предложил последовательность 1, 4, 13, 40, 121 и т.д. (каждое следующее значение на единицу больше утроенного предыдущего). Для набора средних размеров такая последовательность позволяет получить достаточно высокие показатели быстродействия при несложном методе вычисления значений последовательности. На основе эмпирических исследований Кнут для среднего случая получил порядок O(n^5/4), а для худшего случая O(n^3/2). Именно такая последовательность используется в приведенной ниже реализации алгоритма.

{ Сортировка Шелла с применением ряда Кнута }

procedure ShellKnuthSort(aList: TList;

aFirst, aLast: Integer; aCompare: TCompareFunc);

Var

i, j, h, N: Integer;

Temp: Pointer;

Begin

{ Начальное значение h должно быть

близко к 1/9 количества элементов }

h:=1; N:=(aLast - aFirst) div 9;

while h <= N do

h:=h*3 + 1;

{ При каждом проходе цикла значение

шага уменьшается на треть }

while h > 0 do

Begin

{ Выполнить сортировку методом

вставки для каждого подмножества }

for i:=(aFirst + h) to aLast do

Begin

Temp:=aList.List[i];

j:=i;

while (j >= (aFirst+h)) and (aCompare(Temp, aList.List[j-h]) < 0) do

Begin

aList.List[j]:=aList.List[j-h];

Dec(j, h);

end;

aList.List[j]:=Temp;

end;

h:=h div 3;

end;

end;

Ряд других последовательностей позволяет получить более высокие показатели, но требуют предварительного вычисления значений последовательности, поскольку формулы вычисления более сложные. В качестве примера приведем самую быструю и известную на сегодня последовательность, разработанную Робертом Седжвиком: 1, 5, 19, 41, 109 и т.д. Последовательность формируется путем слияния двух последовательностей – 9*4*i-9*2*i+1 для i > 0 и 4*i-3*2*i+1 для i > 1. Для этой последовательности в худшем случае порядок равен O(n^4/3) и в среднем случае O(n^7/6).

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