Фундаментальные алгоритмы и структуры данных в Delphi
Шрифт:
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% меньше времени, чем стандартный.
Сортировка слиянием для связных списков
Последним алгоритмом, который мы рассмотрим в этой главе, снова будет сортировка слиянием, но в этот раз применительно к связным спискам. Как вы, наверное, помните, несмотря на высокие показатели быстродействия (алгоритм класса O(n log(n))), использование сортировки слиянием требует наличия вспомогательного массива, размер которого составляет половину размера сортируемого массива. Такая необходимость вызвана тем, что на этапе слияния сортировке нужно куда-то помещать элементы.
Для связных списков сортировка слиянием не требует наличия вспомогательного массива, поскольку элементы можно свободно перемещать, разрывая и восстанавливая связи, с быстродействием O(1), т.е. за постоянное время.
Код для сортировки связных списков можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDLnkLst.pas.
Давайте рассмотрим, каким образом работает код для односвязных списков, а затем расширим концепцию для двухсвязных списков.
Предположим, что имеется связный список с фиктивным начальным узлом. (С учетом этого предположения алгоритм сортировки намного упрощается.) Таким образом, каждый сортируемый нами узел будет иметь родительский узел. Рассмотрим процесс слияния. Пусть имеются два списка, описываемых родительскими узлами первых узлов. Будем считать, что оба списка отсортированы. Можно легко разработать алгоритм слияния с целью объединения двух списков в один. При этом процесс слияния будет заключаться в выполнении удалений и вставок.
Сравниваем два элемента, на которые указывают два родительских узла. Если меньший элемент находится в первом узле, он находится на своем месте, поэтому переходим к следующему узлу. При этом первый узел будет новым родительским узлом. Если же меньший элемент находится во втором списке, его необходимо удалить из списка и вставить после родительского узла первого списка, а затем перейти к следующему узлу. При этом вновь вставленный узел будет новым родительским узлом. Далее описанный процесс продолжается вплоть до исчерпания улов одного из списков. Если пройден весть первый список, в него добавляются оставшиеся элементы из второго.