Бакнелл Джулиан М.
Шрифт:
function TtdDoubleLinkList.dllMerge(aCompare : TtdCompareFunc;
aPriorNode1: PdlNode;
aCount1 : longint;
aPriorNode2: PdlNode;
aCount2 : longint);
PdlNode;
var
i : integer;
Node1 : PdlNode;
Node2 : PdlNode;
LastNode : PdlNode;
Temp : PdlNode;
begin
LastNode := aPriorNode1;
{извлечь первые два узла}
Node1 := aPriorNode1^.dlnNext;
Node2 := aPriorNode2^.dlnNext;
{повторять до тех nop, пока один из списков не опустеет}
while (aCount1 <> 0) and (aCount2 <> 0) do
begin
if (aCompare(Node1^.dlnData, Node2^.dlnData) <= 0) then begin
LastNode := Node1;
Node1 := Node1^.dlnNext;
dec(aCount1);
end
else begin
Temp := Node2^.dlnNext;
Node2^.dlnNext := Node1;
LastNode^.dlnNext := Node2;
LastNode := Node2;
Node2 := Temp;
dec(aCount2);
end;
end;
{если закончились элементы в первом списке, связать последний узел с оставшейся частью второго списка и пройти список до последнего узла}
if (aCount1 = 0) then begin
LastNode^.dlnNext := Node2;
for i := 0 to pred(aCount2) do LastNode := LastNode^.dlnNext;
end
{если закончились элементы во втором списке, то Node2 будет первым узлом в оставшемся списке;пройти список до последнего узла и связать его с узлом Node2}
else begin
for i := 0 to pred(aCount1) do LastNode := LastNode^.dlnNext;
LastNode^.dlnNext := Node2;
end;
{вернуть последний узел}
Result := LastNode;
end;
function TtdDoubleLinkList.dllMergesort(aCompare : TtdCompareFunc;
aPriorNode : PdlNode; aCount : longint): PdlNode;
var
Count2 : longint;
PriorNode2 : PdlNode;
begin
{сначала обрабатывается простой случай: если в списке всего один элемент, он отсортирован, поэтому выполнение функции завершается}
if (aCount = 1) then begin
Result := aPriorNode^.dlnNext;
Exit;
end;
{разбить список на две части}
Count2 := aCount div 2;
aCount := aCount - Count2;
{выполнить сортировку слиянием первой половины: вернуть начальный узел для второй половы}
PriorNode2 := dllMergeSort(aCompare, aPriorNode, aCount);
{выполнить сортировку слиянием второй половины}
dllMergeSort(aCompare, PriorNode2, Count2);
{объединить две половины}
Result := dllMerge(aCompare, aPriorNode, aCount, PriorNode2, Count2);
end;
procedure TtdDoubleLinkList.Sort(aCompare : TtdCompareFunc);
var
Dad, Walker : PdlNode;
begin
{если в списке больше одного элемента, выполнить сортировку для односвязного списка, а затем восстановить обратные ссылки}
if (Count > 1) then begin
dllMergesort(aCompare, FHead, Count);
Dad := FHead;
Walker := FHead^.dlnNext;
while (Walker <> nil) do
begin
Walker^.dlnPrior := Dad;
Dad := Walker;
Walker := Dad^.dlnNext;
end;
end;
MoveBeforeFirst;
FIsSorted := true;
end;
Резюме
В этой главе мы рассмотрели различные алгоритмы сортировки и изучили особенности и характеристики каждого из них. Были описаны базовые алгоритмы: пузырьковая сортировка, шейкер-сортировка и сортировка методом вставок, и было показано, что они принадлежат к классу O(n(^2^)). Затем были описаны два алгоритма со средним быстродействием: сортировка методом Шелла и сортировка прочесыванием. Их анализ был сложнее, чем для алгоритмов первой группы, но они были быстрее базовых алгоритмов. И, наконец, были рассмотрены два самых быстрых метода сортировки: сортировка слиянием и быстрая сортировка, которые принадлежат к классу O(n log(n)). Было показано, что в отличие от всех других методов, сортировка слиянием требует организации вспомогательного массива.
Для быстрой сортировки мы рассмотрели целый ряд возможных улучшений, подробно описывая каждое из них и оценивая его влияние на время выполнения алгоритма. Улучшения не оказывали влияния на функцию быстродействия алгоритма в контексте О-нотации, но, тем не менее, приводили к снижению константы пропорциональности, тем самым увеличивая скорость работы алгоритма.
И, наконец, было показано, каким образом сортировка слиянием применяется в отношении связных списков. В этом случае она не требует наличия вспомогательного массива и позволяет достичь максимальной эффективности.