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

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

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

procedure QSM(aList : TList;

aFirst : integer;

aLast : integer;

aCompare : TtdCompareFunc);

var

L, R : integer;

Pivot : pointer;

Temp : pointer;

begin

while (aFirst < aLast) do

begin

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

if (aLast - aFirst) >= 2 then

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;

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