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

begin

R := (aFirst + aLast) div 2;

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

begin

Temp := aList.List^[aFirst];

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

aList.List^[R] :=Temp;

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;

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;

Pivot :-aList,List^[R];

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

Pivot := aList.List^[ aFirst ];

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

L := pred( aFirst);

R := succ(aLast);

while true do

begin

repeat

dec (R);

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

repeat

inc(L);

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] := Teilend;

{выполнить быструю сортировку первого подфайла}

if (aFirst < R) then

QSM(aList, aFirst, R, aCompare);

{выполнить быструю сортировку второго подфайла - устранение рекурсии}

aFirst := succ(R);

end;

end;

procedure TDQuickSortMedian( aList : TList;

aFirst : integer;

aLast : integer;

aCompare : TtdCompareFunc);

begin

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

QSM(aList, aFirst, aLast, aCompare);

end;

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

Сортировка трех выбранных элементов выполняется на основе одного малоизвестного и малоиспользуемого метода. Предположим, что выбраны элементы a, b и c. Сравниваем а и b. Если b меньше чем я, поменять их местами. Таким образом, получим a < b. Сравниваем a и c. Если c меньше чем a, поменять их местами. Получим a < c. После выполнения этих сравнений нам будет известно, что элемент a содержит минимальное значение из трех выбранных элементов, поскольку оно меньше или равно значениям элементов b и c. Сравниваем b и с. Если с меньше чем b, поменять их местами. Теперь элементы расположены в порядке a< b

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

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

Рассмотрим рекурсивный вызов. Задаются четыре параметра, два из которых постоянны, а два других от вызова к вызову могут изменяться. Постоянные параметры - aList и aCompare, переменные параметры - aFirst и aSecond. Рекурсивный вызов можно устранить за счет использования явного стека, который предназначен для заталкивания и выталкивания переменных параметров. При этом цикл будет выполняться до тех пор, пока стек не будет пустым.

Листинг 5.17. Быстрая сортировка со случайным выбором базового элемента

procedure QSNR(aList : TList;

aFirst : integer;

aLast : integer;

aCompare : TtdCompareFunc);

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 (aFirst < aLast) do

begin

{в качестве базового выбирается средний элемент}

Pivot := aList.List^[ (aFirst+aLast) div 2];

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

L := pred(aFirst);

R := succ(aLast);

while true do

begin

repeat

dec(R);

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

repeat

inc(L);

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(SP, 2);

aFirst := succ(R);

end;

end;

end;

end;

procedure TDQuickSortNoRecurse( aList : TList;

aFirst : integer;

aLast : integer;

aCompare : TtdCompareFunc);

begin

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

QSNR(aList, aFirst, aLast, aCompare);

end;

И в этом листинге код состоит из двух процедур: процедуры-драйвера и процедуры собственно сортировки. Таким образом, общая схема работы алгоритма осталась неизменной, но в этом случае внутренняя процедура, QSNR, вызывается только один раз.