Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi

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)). Было показано, что в отличие от всех других методов, сортировка слиянием требует организации вспомогательного массива.

Для быстрой сортировки мы рассмотрели целый ряд возможных улучшений, подробно описывая каждое из них и оценивая его влияние на время выполнения алгоритма. Улучшения не оказывали влияния на функцию быстродействия алгоритма в контексте О-нотации, но, тем не менее, приводили к снижению константы пропорциональности, тем самым увеличивая скорость работы алгоритма.

И, наконец, было показано, каким образом сортировка слиянием применяется в отношении связных списков. В этом случае она не требует наличия вспомогательного массива и позволяет достичь максимальной эффективности.

Возможно, у кого-то из вас, кто просто листал эту книгу и случайно наткнулся на данную главу, возник вопрос, что же такое рандомизированные алгоритмы! Это алгоритмы, работающие случайным образом? Ничего подобного. Здесь термин рандомизированный алгоритм (randomized algorithm) употребляется в отношении алгоритма, который генерирует или использует случайные числа.

Если вы на минутку отвлечетесь и подумаете над выражением "генерация случайных чисел", то, скорее всего, придете к выводу, что оно не имеет смысла. Компьютеры - это детерминированные машины: если существует определенная программа или функция, предназначенная для выполнения определенной работы, то для одного и того же набора входных данных она будет давать один и тот же набор выходных данных. (Если это не так, компьютер можно преспокойно отправлять в ремонт.) Без использования специального оборудования для генерации случайных чисел программные генераторы также представляют собой всего-навсего функции. Каким же образом вычисляемые ими числа могут быть случайными? Если запустить генератор в некотором определенном состоянии, то, изучив исходный код генератора, можно предсказать всю последовательность генерируемых им случайных чисел. Какие же это случайные числа? Скоро мы более подробно обсудим эту дилемму.

В состав ядра операционной системы Linux входит модуль, который анализирует, каким образом пользователь вводит данные с клавиатуры и оценивает интервал между нажатиями клавиш, а затем использует полученные данные для вычисления рандомизирующего коэффициента. Подобным образом генераторы случайных чисел, имеющиеся в ядре, дают более "случайные" последовательности значений.

С применением случайных чисел в алгоритмах мы уже встречались в главе 5: алгоритм быстрой сортировки со случайным выбором базового элемента. Причина, по которой в алгоритме сортировки использовались случайные числа, состояла в том, что этот алгоритм, несмотря на его высокие общие характеристики, обладает очень низкими характеристиками в худшем случае. За счет применения случайных чисел можно значительно снизить вероятность попадания на сценарий худшего случая. В этой главе мы рассмотрим новую структуру данных - списки с пропусками, которые представляют собой метод организации отсортированных связных списков с помощью случайных чисел, что существенно увеличивает скорость выполнения операции вставки нового элемента.

Есть и другие алгоритмы, использующие случайные числа. Необходимость применения случайных чисел бывает вызвана, как правило, двумя причинами: 1) пространство решений алгоритма очень велико и поиск определенного решения будет выполняться слишком медленно, 2) существует необходимость моделирования физической системы для ее оптимизации и т.п.

Все исходные коды для генераторов случайных чисел можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDRandom.pas.