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

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.

Генерация случайных чисел

Прежде всего, давайте опишем, что мы понимаем под случайным числом (random number). Без четкого определения термина мы будем неуверенно себя чувствовать при разработке и реализации генератора случайных чисел.