aPriorNode : PslNode;
aCount : longint): PslNode;
var
Count2 : longint;
PriorNode2 : PslNode;
begin
{сначала обрабатывается простой случай: если в списке всего один элемент, он отсортирован, поэтому выполнение функции завершается}
if (aCount = 1) then begin
Result := aPriorNode^.slnNext;
Exit;
end;
{разбить список на две части}
Count2 := aCount div 2;
aCount := aCount - Count2;
{выполнить сортировку слиянием первой половины: вернуть начальный узел для второй половины}
PriorNode2 := sllMergeSort(aCompare, aPriorNode, aCount);
{выполнить сортировку слиянием второй половины}
sllMergeSort(aCompare, PriorNode2, Count2);
{объединить две половины}
Result := sllMerge(aCompare, aPriorNode, aCount, PriorNode2, Count2);
end;
Метод сортировки слиянием вызывается с указанием начального узла сортируемого списка и количества узлов в списке. Имея такие входные данные, за счет прохождения списка и подсчета узлов можно определить, где начинается вторая половина списка. В качестве возвращаемого параметра после сортировки первой половины списка используется последний узел первой половины, который служит фиктивным начальным узлом для второй половины. В любом случае нам приходится проходить список. Тогда почему бы нам заодно не определить положение средней точки?
И последняя часть реализации сортировки - сама функция слияния. Ее код приведен в листинге 5.21. Она не представляет никаких трудностей для понимания. Начальным узлом объединенного списка будет служить родительский узел первого подсписка. Функция возвращает последний элемент объединенного списка (он будет использоваться в качестве родительского узла для несортированной части подсписка).
Листинг 5.21. Фаза слияния при сортировке слиянием односвязного списка
function TtdSingleLinkList.sllMerge( aCompare : TtdCompareFunc;
aPriorNode1 : PslNode; aCount1 : longint;
aPriorNode2 : PslNode; aCount2 : longint): PslNode;
var
i : integer;
Node1 : PslNode;
Node2 : PslNode;
LastNode : PslNode;
Temp : PslNode;
begin
LastNode := aPriorNode1;
{извлечь первые два узла}
Node1 := aPriorNode1^.slnNext;
Node2 := aPriorNode2^.slnNext;
{повторять цикл до исчерпания элементов одного из списков}
while (aCount1 <> 0) and (aCount2<> 0) do
begin
if (aCompare(Node1^.slnData, Node2^.slnData) <= 0) then begin
LastNode := Node1;
Node1 := Node1^.slnNext;
dec(aCount1);
end
else begin
Temp := Node2^.slnNext;
Node2^.slnNext := Node1;
LastNode^.slnNext := Node2;
LastNode := Node2;
Node2 := Temp;
dec(aCount2);
end;
end;
{если закончились элементы в первом списке, связать последний узел с оставшейся частью второго списка и пройти список до последнего узла}
if (aCount1 = 0) then begin
LastNode^.slnNext := Node2;
for i := 0 to pred(aCount2) do LastNode := LastNode^.slnNext;
end
{если закончились элементы во втором списке, то Node2 будет первым узлом в оставшемся списке; пройти список до последнего узла и связать его с узлом Node2}
else begin
for i := 0 to pred(aCount1) do
LastNode := LastNode^.slnNext;
LastNode^.slnNext := Node2;
end;
{вернуть последний узел}
Result := LastNode;
end;
Обратите внимание, что в односвязном списке сортировка слиянием не требует выполнения обратного прохода. Мы не были в ситуации, когда требовалось знание родительского узла определенного узла, а он не был известен. Это означает, что сортировка слиянием в двухсвязном списке может выполняться точно так же, как и в односвязном, но после сортировки нужно будет пройти весь список и восстановить обратные ссылки.
Листинг 5.22. Сортировка слиянием для двухсвязного списка
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)). Было показано, что в отличие от всех других методов, сортировка слиянием требует организации вспомогательного массива.
Для быстрой сортировки мы рассмотрели целый ряд возможных улучшений, подробно описывая каждое из них и оценивая его влияние на время выполнения алгоритма. Улучшения не оказывали влияния на функцию быстродействия алгоритма в контексте О-нотации, но, тем не менее, приводили к снижению константы пропорциональности, тем самым увеличивая скорость работы алгоритма.
И, наконец, было показано, каким образом сортировка слиянием применяется в отношении связных списков. В этом случае она не требует наличия вспомогательного массива и позволяет достичь максимальной эффективности.
Глава 6. Рандомизированные алгоритмы.
Возможно, у кого-то из вас, кто просто листал эту книгу и случайно наткнулся на данную главу, возник вопрос, что же такое рандомизированные алгоритмы! Это алгоритмы, работающие случайным образом? Ничего подобного. Здесь термин рандомизированный алгоритм (randomized algorithm) употребляется в отношении алгоритма, который генерирует или использует случайные числа.
Если вы на минутку отвлечетесь и подумаете над выражением "генерация случайных чисел", то, скорее всего, придете к выводу, что оно не имеет смысла. Компьютеры - это детерминированные машины: если существует определенная программа или функция, предназначенная для выполнения определенной работы, то для одного и того же набора входных данных она будет давать один и тот же набор выходных данных. (Если это не так, компьютер можно преспокойно отправлять в ремонт.) Без использования специального оборудования для генерации случайных чисел программные генераторы также представляют собой всего-навсего функции. Каким же образом вычисляемые ими числа могут быть случайными? Если запустить генератор в некотором определенном состоянии, то, изучив исходный код генератора, можно предсказать всю последовательность генерируемых им случайных чисел. Какие же это случайные числа? Скоро мы более подробно обсудим эту дилемму.
В состав ядра операционной системы Linux входит модуль, который анализирует, каким образом пользователь вводит данные с клавиатуры и оценивает интервал между нажатиями клавиш, а затем использует полученные данные для вычисления рандомизирующего коэффициента. Подобным образом генераторы случайных чисел, имеющиеся в ядре, дают более "случайные" последовательности значений.
С применением случайных чисел в алгоритмах мы уже встречались в главе 5: алгоритм быстрой сортировки со случайным выбором базового элемента. Причина, по которой в алгоритме сортировки использовались случайные числа, состояла в том, что этот алгоритм, несмотря на его высокие общие характеристики, обладает очень низкими характеристиками в худшем случае. За счет применения случайных чисел можно значительно снизить вероятность попадания на сценарий худшего случая. В этой главе мы рассмотрим новую структуру данных - списки с пропусками, которые представляют собой метод организации отсортированных связных списков с помощью случайных чисел, что существенно увеличивает скорость выполнения операции вставки нового элемента.
