Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi

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

Представьте себе, что разбиваются только подсписки размером не менее определенного количества элементов. К чему бы привел такой алгоритм быстрой сортировки? Мы получим грубо отсортированный список, т.е. все его элементы будут находиться вблизи требуемых позиций. Подсписки, которые были получены перед прекращением процесса разбиения, будут отсортированы в том смысле, что если подсписок X находится перед подсписком Y, то все элементы подсписка X будут расположены в отсортированном списке перед элементами подсписка Y. Это как раз самое удобное распределение для сортировки методом вставок. Таким образом, работу, начатую быстрой сортировкой, можно завершить с помощью сортировки методом вставок.

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

Листинг 5.18. Оптимизированная быстрая сортировка

const

QSCutOff = 15;

procedure QSInsertionSort(aList : TList;

aFirst : integer; aLast : integer;

aCompare : TtdCompareFunc);

var

i, j : integer;

IndexOfMin : integer;

Temp : pointer;

begin

{найти элемент с наименьшим значением из первых QSCutOff элементов и переместить его на первую позицию}

IndexOfMin := aFirst;

j := QSCutOff;

if (j > aLast) then

j := aLast;

for i := succ(aFirst) to j do

if (aCompare(aList.List^[i], aList.List^[IndexOfMin]) < 0) then

IndexOfMin := i;

if (aFirst <> indexOfMin) then begin

Temp := aList.List^[aFirst];

aList.List^[aFirst] := aList.List^[IndexOfMin];

aList.List^[IndexOfMin] := Temp;

end;

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

for i := aFirst+2 to aLast do

begin

Temp := aList.List^[i];

j := i

while (aCompare(Temp, aList.List^[j-1]) < 0) do

begin

aList.List^[j] := aList.List^[j-1];

dec(j);

end;

aList.List^ [j ] :=Temp;

end;

end;

procedure QS( aList : TList;

aFirst : integer;

aLast : integer;

aCompare : TtdComparSFunc);

var

L, R : integer;

Pivot : pointer;

Temp : pointer;

Stack : array [0..63] of integer;

{позволяет разместить до 2 миллиардов элементов}

SP : integer;

begin

{инициализировать стек}

Stack[0] := aFirst;

Stack[1] := aLast;

SP := 2;

{пока в стеке есть подфайлы}

while (SP<> 0) do

begin

{вытолкать верхний подфайл}

dec(SP, 2);

aFirst := Stack[SP];

aLast := Stack[SP+1];

{повторять пока в подфайле есть достаточное количество элементов}

while ((aLast - aFirst) > QSCutOff) do

begin

{выполнить сортировку первого, среднего и последнего элементов и в качестве базовой точки выбрать средний - метод медианы трех}

R := (aFirst + aLast) div 2;

if aCompare(aList.List^[aFirst], aList.List^[R]) > Othen begin

Temp := aList.List^[aFirst];

aList.List^[aFirst] := aList.List^[R];

aList.List^[R] := Temp;

end;

if aCompare(aList.List^[aFirst], aList.List^[aLast]) > 0 then begin

Temp := aList.List^[aFirst];

aList.List^[aFirst] := aList.List^[aLast];

aList.List^ [aLast] := Temp;

end;

if aCompare(aList.List^[R], aList.List^[aLast]) > 0 then begin

Temp := aList.List^[R];

aList.List^[R] := aList.List^[aLast];

aList.List^ [aLast] :=Temp;

end;

Pivot := aList.List^[R];

{задать начальные значения индексов и приступить к разбиению списка}

L := aFirst;

R := aLast;

while true do

begin

repeat

dec(R);

until (aCompare(aList.List^[R], Pivot) <=0);

repeat

inc(1);

until (aCompare(aList.List^[L], Pivot) >=0);

if (L >= R) then

Break;

Temp := aList.List^[L];

aList.List^[L] := aList.List^[R];

aList.List^[R] :=Temp;

end;

{затолкнуть больший подфайл в стек и повторить цикл для меньшего подфайла}

if (R - aFirst) < (aLast - R) then begin

Stack[SP] :=succ(R);

Stack[SP+1] := aLast;

inc(SP, 2);

aLast := R;

end

else begin

Stack[SP] := aFirst;

Stack [SP+1] :=R;

inc(SPs 2);

aFirst := succ(R);

end;

end;

end;

end;

procedure TDQuickSort( aList : TList;

aFirst : integer; aLast : integer;

aCompare : TtdCompareFunc);

begin

TDValidateListRange(aList, aFirst, aLast, 'TDQuickSort');

QS(aList, aFirst, aLast, aCompare);

QSInsertionSort(aList, aFirst, aLast, aCompare);

end;

Эта оптимизированная быстрая сортировка состоит из трех процедур. Первая из них - вызываемая процедура TDQuickSort. Она проверяет корректность переданных параметров, для частично сортировки списка вызывает процедуру QS, а затем для окончательной сортировки вызывает процедуру QSInsertionSort. Процедура QS выполняет нерекурсивный процесс разбиения списка до получения подсписков определенного минимального размера. QSInsertionSort представляет собой процедуру оптимизированной сортировки методом вставок для частично отсортированного списка. В частности, обратите внимание, что элемент с наименьшим значением находится в первых QSCutOf f элементах списка. Это вызвано выполнением процесса разбиения и тем фактом, что при достижении размеров подсписков QSCutOff элементов разбиение прекращается.

Стоила ли игра свеч? Тесты однозначно показывают, что стоила. При сортировке 100000 элементов типа longint оптимизированный алгоритм сортировки потребовал на 18% меньше времени, чем стандартный.