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

• Название: Фундаментальные алгоритмы и структуры данных в Delphi
• Автор: Джулиан Бакнелл
• Издательство: ДиаСофтЮП
• Жанр: Программирование
• Год: 2003
• ISBN: ISBN 5-93772-087-3

Книга "Фундаментальные алгоритмы и структуры данных в Delphi" представляет собой уникальное учебное и справочное пособие по наиболее распространенным алгоритмам манипулирования данными, которые зарекомендовали себя как надежные и проверенные многими поколениями программистов. По данным журнала "Delphi Informant" за 2002 год, эта книга была признана сообществом разработчиков прикладных приложений на Delphi как «самая лучшая книга по практическому применению всех версий Delphi».

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

Несмотря на то что книга рассчитана в первую очередь на профессиональных разработчиков приложений на Delphi, она окажет несомненную пользу и начинающим программистам, демонстрируя им приемы и трюки, которые столь популярны у истинных «профи». Все коды примеров, упомянутые в книге, доступны для выгрузки на Web-сайте издательства.

---

С описанным алгоритмом связана только одна проблема. Если рассматривать тасование с другой точки зрения, с позиции главных принципов, можно показать, что для первой позиции можно выбрать один из n элементов. После этого для второй позиции останется выбор только из n - 1 элементов. Далее для третьей позиции элементов будет уже n - 2 и т.д. В результате таких рассуждений можно прийти к выводу, что общее количество возможных комбинаций будет вычисляться как n! (n! означает n факториал и сводится к произведению n * (n- 1) * (n-2) *...* 1.)

Вернемся к проблеме: если не брать во внимание случай, когда n = 1, n(^n^) больше, а часто намного больше, чем n! Таким образом, с помощью описанного алгоритма формируются повторяющиеся последовательности, причем некоторые из них будут повторяться чаще, нежели другие, поскольку n(^n^) не делится на n! без остатка.

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

Листинг 5.3. Корректный метод тасования массива TList

procedure TDListShuffle(aList : TList; aStart, aEnd : integer);

var

Range : integer;

Inx : integer;

RandomInx : integer;

TempPtr : pointer;

begin

TDValidateListRange(aList, aStart, aEnd, 'TDListShuffle');

{для каждого элемента, считая справа...}

for Inx := (aEnd - aStart) downto aStart + 1 do

begin

{сгенерировать случайное число из диапазона от aStart до текущего индекса}

RandomInx := aStart + Random(Inx-aStart+ 1);

{если случайный индекс не равен текущему, переставить элементы}

if (RandomInx <> Inx) then begin

TempPtr := aList.List^[Inx];

aList.List^[Inx] := aList.List^[RandomInx];

aList.List^ [RandomInx] TempPtr;

end;

end;

end;

Основы сортировки

Алгоритмы сортировки можно разделить на два типа: устойчивые и неустойчивые. К устойчивой сортировке относятся те алгоритмы, которые при наличии в наборе данных нескольких равных элементов в отсортированном наборе оставляют их в том же порядке, в котором эти элементы были в исходном наборе. Например, предположим, что в наборе имеется три элемента и значение каждого элемента равно 42 (т.е. элементы равны). Пусть в исходном наборе элемент А находится в позиции 12, элемент В - в позиции 234, а С - в позиции 3456. После выполнения устойчивой сортировки они будут находиться в последовательности А, В, С, т.е. их взаимный порядок не изменится. С другой стороны, неустойчивая сортировка не гарантирует, что элементы с равными значениями будут находиться в определенной последовательности. Для нашего примера элементы А, В и С могут оказаться в последовательности А, В, С, или С, В, А, или любой другой.

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

Каждый из алгоритмов сортировки с целью упрощения понимания будет описан на примере сортировки колоды карт. Выберите все черви из колоды и перетасуйте их (манипулирование только 13 картами позволит упростить вашу работу).

Самые медленные алгоритмы сортировки

Мы будет рассматривать все алгоритмы сортировки, разделяя их на три группы. К первой группе отнесем медленные алгоритмы, принадлежащие к классу O(n(^2^)), хотя парочка из них в отдельных ситуациях на определенных распределениях данных дает очень высокие показатели производительности.

Пузырьковая сортировка

Первый алгоритм, с которым сталкиваются все программисты при изучении азов программирования, - это пузырьковая сортировка (bubble sort). Как это ни прискорбно, но из всех известных алгоритмов пузырьковая сортировка является самой медленной. Хотя, возможно, ее легче запрограммировать, чем другие алгоритмы сортировки (хотя и не намного).

Рисунок 5.1. Один проход с помощью алгоритма пузырьковой сортировки

Пузырьковая сортировка работает следующим образом. Разложите ваши карты (помните, что их всего 13?). Посмотрите на двенадцатую и тринадцатую карту. Если двенадцатая карта старше тринадцатой, поменяйте их местами. Теперь перейдите к одиннадцатой и двенадцатой картам. Если одиннадцатая карта старше двенадцатой, поменяйте их местами. То же сделайте и для пар (10, 11), (9, 10) и т.д., пока не дойдете до первой и второй карты. После первого прохода по всей колоде туз окажется на первой позиции. Фактически когда вы "зацепились" за туз он "выплыл" на первую позицию. Теперь вернитесь к двенадцатой и тринадцатой картам. Выполните описанный выше процесс, на этот раз остановившись на второй и третьей картах. Обратите внимание, что вам удалось переместить двойку на вторую позицию. Продолжайте процесс сортировки, уменьшая с каждым новым циклом количество просматриваемых карт и поступая так до тех пор, пока вся колода не будет отсортирована.

Полагаем, вы согласитесь с тем, что сортировка была довольно-таки утомительной. При реализации алгоритма на языке Pascal "утомительность" выражается медленной скоростью работы. Тем не менее, существует один простой метод оптимизации пузырьковой сортировки: если при выполнении очередного прохода не было выполнено ни одной перестановки, значит, карты уже отсортированы в требуемом порядке.

Листинг 5.4. Пузырьковая сортировка

procedure TDBubbleSort(aList : TList;

aFirst : integer;

aLast : integer;

aCompare : TtdCompareFunc);

var

i, j : integer;

Temp : pointer;

Done : boolean;

begin

TDValidateListRange(aList, aFirst, aLast, 'TDBubbleSort');

for i := aFirst to pred(aLast) do

begin

Done := true;

for j := aLast downto succ ( i ) do

if (aCompare(aList.List^[j], aList.List^ ) < 0) then begin

{переставить j-ый и (j - 1)-ый элементы}

Temp := aList.List^ [ j ];

aList.List^[j] := aList.List^[j-1];

aList.List^[j-1] :=Temp;

Done := false;

end;

if Done then

Exit;

end;

end;

Пузырьковая сортировка принадлежит к алгоритмам класса O(n(^2^)). Как видите, в реализации присутствуют два цикла: внешний и внутренний, при этом количество выполнений каждого цикла зависит от количества элементов в массиве. При первом выполнении внутреннего алгоритма будет произведено n - 1 сравнений, при втором — n - 2, при третьем — n - 3 и т.д. Всего будет n - 1 таких циклов, таким образом, общее количество сравнений составит:

(n-1) + (n-2)+... + 1

Приведенную сумму можно упростить до n (n - 1)/2 или (n(^2^) - n)/2. Другими словами, получаем O(n(^2^)). Количество перестановок вычислить несколько сложнее, но в худшем случае (когда элементы в исходном наборе были отсортированы в обратном порядке) количество перестановок будет равно количеству сравнений, т.е. снова получаем O(n(^2^)).

Небольшая оптимизация метода пузырьковой сортировки, о которой мы говорили чуть выше, означает, что если элементы в наборе уже отсортированы в нужном порядке, пузырьковая сортировка будет выполняться очень быстро: будет выполнен всего один проход по списку, не будет сделано ни одной перестановки и выполнение алгоритма завершится, (n -1) сравнений и ни одной перестановки говорят о том, что в лучшем случае быстродействие пузырьковой сортировки равно O(n).

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

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

Шейкер-сортировка

Пузырьковая сортировка имеет одну малоизвестную вариацию, которая на практике дает незначительное увеличение скорости, - это так называемая шейкер-сортировка (shaker sort).

Рисунок 5.2. Два прохода с помощью шейкер-сортировки

Вернемся к картам. Выполните первый проход согласно алгоритму сортировки. Туз попадет на первую позицию. Теперь, вместо прохода колоды карт справа налево, пройдите слева направо: сравните вторую и третью карты и старшую карту поместите на третью позицию. Сравните третью и четвертую карты, и при необходимости поменяйте их местами. Продолжайте сравнения вплоть до достижения пары (12, 13). По пути к правому краю колоды вы "захватили" короля и переместили его на последнюю позицию.

А теперь снова пройдите колоду справа налево до второй карты. Во вторую позицию попадет двойка. Продолжайте чередовать направления проходов до тех пор, пока не будет отсортирована вся колода.