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

Прежде всего, давайте изучим влияние выбора базового элемента на быстродействие алгоритма. Если вы помните, в нашей первой процедуре быстрой сортировки в качестве базового элемента выбирался средний элемент. До этого мы коротко рассмотрели и отклонили выбор первого и последнего элемента списка. В идеальном случае следовало бы каждый раз выбирать средний элемент отсортированного списка или, в крайнем случае, избегать выбора в( качестве базового элемента с минимальным и максимальным значением (поскольку в этом случае быстрая сортировка вырождается в длинную серию пустых подсписков и подсписков с одним или меньшим количеством элементов). Часто в качестве базового элемента выбирается случайный элемент. Затем этот элемент меняется местом со средним элементом, и алгоритм выполняется, как и в случае выбора среднего элемента.

Что дает нам случайный выбор базового элемента? При условии, что у нас есть достаточно хороший генератор псевдослучайных чисел, такой выбор гарантирует, что вероятность попадания на "худший" элемент становится пренебрежительно малой. Но, тем не менее, она не превращается в 0, просто выбор наихудшего для быстрой сортировки элемента в качестве базового становится весьма маловероятным.

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

procedure QSR(aList : TList;

aFirst : integer;

aLast : integer;

aCompare : TtdCompareFunc);

var

L, R : integer;

Pivot : pointer;

Temp : pointer;

begin

while (aFirst < aLast) do

begin

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

R := aFirst + Random(aLast - aFirst + 1);

L := (aFirst + aLast) div 2;

Pivot := aList.List^[R];

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

aList.List^[L] := Pivot;

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

L := pred( aFirst);

R := succ(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

Brealc-Temp := aList.List^[L];

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

aList.List^[R] := Temp;

end;

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

if (aFirst < R) then

QSR(aList, aFirst, R, aCompare);

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

aFirst :=succ(R);

end;

end;

procedure TDQuickSortRandom(aList : TList;

aFirst : integer;

aLast : integer;

aCompare : TtdCompareFunc);

begin

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

QSR(aList, aFirst, aLast, aCompare);

end;

Как видите, различия между стандартным алгоритмом быстрой сортировки и приведенным в листинге 5.15 совсем незначительны. Основное отличие представляет собой вставленный блок кода, который специально выделен в листинге. В нем первый индекс выбирается случайным образом из диапазона от aFirst до aLast включительно, а затем элемент с выбранным индексом меняется местами со средним элементом. Для удобства в приведенной реализации используется Delphi-функция Random. Она предоставляет хорошие последовательности псевдослучайных чисел. Перестановка выбранного и среднего элементов дает преимущества, о которых мы уже говорили.

Несмотря на то что внесенное изменение снижает вероятность выбора "худшего" элемента при каждом проходе цикла, тем не менее, оно не увеличивает скорость выполнения процедуры. Фактически скорость даже падает (как это и можно было предположить). Генерация случайного числа в качестве индекса для базового элемента работает отлично, в том смысле, что вероятность выбора "плохого" элемента в качестве базового снижается, но это положительное свойство не приводит к повышению быстродействия процедуры. Сложность линейного конгруэнтного метода генерации случайных чисел, используемого функцией Random, только увеличивает время выполнения процедуры. Можно было бы исследовать быстродействие при использовании различных генераторов (некоторые из них будут рассмотрены в главе 6), но оказывается, что существует намного более удачный алгоритм выбора базового элемента.

Самым эффективным методом выбора базового элемента на сегодняшний день является метод медианы трех. Мы уже говорили, что в идеальном случае желательно было бы выбирать средний элемент (или медиану) всех элементов списка. Тем не менее, определение медианы - достаточно сложная задача. Более простым кажется приближенное определение медианы. Для этого из подсписка выбирается три элемента и в качестве базового элемента выбирается медиана этих трех элементов. Медиана трех элементов служит приближением фактической медианы всех элементов списка. Конечно, такой алгоритм предполагает, что в списке должно быть, по крайней мере, три элемента. Но даже если элементов меньше, выполнить их сортировку не представляет большого труда.