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

Begin

Begin

Begin

Begin

Var

Begin

Begin

Begin

Begin

Begin

Var

h, i, t, N: Integer;

Temp: Pointer;

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

k: Boolean;

N:=aList.Count;

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

h:=N div 2;

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

while h > 0 do

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

k:=True;

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

while k do

k:=False;

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

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

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

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

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	Содержимое массива
Исходный		76 22 4 17 13 49 4 18 32 40 96 57 77 20 1 52
		32 22 4 17 13 20 1 18 76 40 96 57 77 49 4 52
		32 22 4 17 13 20 1 18 76 40 96 57 77 49 4 52
		13 20 1 17 32 22 4 18 76 40 4 52 77 49 96 57
		13 20 1 17 32 22 4 18 76 40 4 52 77 49 96 57
		13 20 1 17 32 22 4 18 76 40 4 52 77 49 96 57
		13 20 1 17 32 22 4 18 76 40 4 52 77 49 96 57
		1 17 4 18 4 20 13 22 32 40 76 49 77 52 96 57
		1 17 4 18 4 20 13 22 32 40 76 49 77 52 96 57
		1 4 17 4 18 13 20 22 32 40 49 76 52 77 57 96
		1 4 4 17 13 18 20 22 32 40 49 52 76 57 77 96
		1 4 4 13 17 18 20 22 32 40 49 52 57 76 77 96
		1 4 4 13 17 18 20 22 32 40 49 52 57 76 77 96
Результат		1 4 4 13 17 18 20 22 32 40 49 52 57 76 77 96

В другой реализации сортировки установка элементов в нужные позиции выполняется методом вставок. Строго говоря, здесь метод Шелла работает путем вставки отсортированных подмножеств основного набора. Каждое подмножество формируется за счет выборки каждого 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);

i, j, h, N: Integer;

Temp: Pointer;

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

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

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

while h <= N do

h:=h*3 + 1;

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

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

while h > 0 do

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

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

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

Temp:=aList.List[i];

j:=i;

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

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 ограничиваются в основном статистическими данными. При перестановке далеко отстоящих элементов возможно нарушение порядка следования элементов с равными значениями и поэтому сортировка Шелла относится к группе неустойчивых алгоритмов.

Самые быстрые алгоритмы сортировки широко используются на практике и важно понимать их особенности, чтобы оптимальным образом реализовывать и применять их в различных приложениях.

Поразрядная цифровая сортировка. Алгоритм поразрядной цифровой сортировки относится к распределительным, и требует представления ключей сортируемой последовательности в виде чисел в некоторой системе счисления P. Число проходов равно максимальному числу значащих цифр в числе – D. В каждом проходе анализируется значащая цифра в очередном разряде ключа, начиная с младшего разряда. Все ключи с одинаковым значением этой цифры объединяются в одну группу.

Ключи в группе располагаются в порядке их поступления. После того, как вся исходная последовательность распределена по группам, группы располагаются в порядке возрастания связанных с группами цифр. Процесс повторяется для второй цифры и т.д., пока не будут исчерпаны значащие цифры в ключе. Основание системы счисления P может быть любым, в частном случае 2 или 10. Для системы счисления с основанием P требуется P групп.

Порядок алгоритма качественно линейный – O(n), для сортировки требуется D·n операций анализа цифры. Однако в оценке порядка не учитывается ряд обстоятельств. Во-первых, операция выделения значащей цифры будет простой и быстрой только при P=2, для других систем счисления эта операция может оказаться значительно более времяемкой, чем операция сравнения. Во-вторых, в оценке алгоритма не учитываются расходы времени и памяти на создание и ведение групп.

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

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

Дата добавления: 2014-01-07