Фундаментальные алгоритмы и структуры данных в Delphi
Шрифт:
Обратите внимание, что такое же улучшение можно было ввести и в рекурсивный алгоритм сортировки. При этом внутренняя процедура быстрой сортировки вызывалась бы для меньшего списка. Внесенное нами небольшое изменение гарантирует, что стек не будет переполнен, если алгоритм быстрой сортировки будет работать на "наихудшем" списке элементов.
Таким образом, нам удалось избавиться от рекурсии, но, как ни странно, экономия времени оказалась незначительной. Более того, в некоторых случаях последний алгоритм работает
Может быть, у некоторых читателей после изучения кода, приведенного в листинге 5.16, возникла идея написания кода, который бы выполнялся в случае, когда в подсписке находится менее трех элементов. Это и будет нашей следующей областью внесения изменений в алгоритм быстрой сортировки.
Следуя тому же ходу мыслей, что и для сортировки слиянием, можно сказать, что быстрая сортировка будет пытаться сортировать все меньшие и меньшие подсписки, которые эффективнее было бы обрабатывать с помощью других методов.
Представьте себе, что разбиваются только подсписки размером не менее определенного количества элементов. К чему бы привел такой алгоритм быстрой сортировки? Мы получим грубо отсортированный список, т.е. все его элементы будут находиться вблизи требуемых позиций. Подсписки, которые были получены перед прекращением процесса разбиения, будут отсортированы в том смысле, что если подсписок 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