Фундаментальные алгоритмы и структуры данных в Delphi
Шрифт:
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: алгоритм быстрой сортировки со случайным выбором базового элемента. Причина, по которой в алгоритме сортировки использовались случайные числа, состояла в том, что этот алгоритм, несмотря на его высокие общие характеристики, обладает очень низкими характеристиками в худшем случае. За счет применения случайных чисел можно значительно снизить вероятность попадания на сценарий худшего случая. В этой главе мы рассмотрим новую структуру данных - списки с пропусками, которые представляют собой метод организации отсортированных связных списков с помощью случайных чисел, что существенно увеличивает скорость выполнения операции вставки нового элемента.
Есть и другие алгоритмы, использующие случайные числа. Необходимость применения случайных чисел бывает вызвана, как правило, двумя причинами: 1) пространство решений алгоритма очень велико и поиск определенного решения будет выполняться слишком медленно, 2) существует необходимость моделирования физической системы для ее оптимизации и т.п.
Все исходные коды для генераторов случайных чисел можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDRandom.pas.