Фундаментальные алгоритмы и структуры данных в Delphi
Шрифт:
Ситуация, в которой мы сейчас находимся, напоминает замкнутый круг (для тестирования алгоритмов сортировки и определения их эффективности необходимы наборы отсортированных данных, но как их получить?), однако два набора отсортированных данных можно сформировать очень просто. Первый набор, используемый при тестировании алгоритмов, случайная последовательность, заслуживает отдельного рассмотрения. Как это ни парадоксально, но обсуждение сортировки мы начнем с описания методов перестановки данных с целью получения случайной последовательности. Выражаясь языком физики, сейчас мы научимся увеличивать энтропию, перед тем как показать, как ее уменьшать.
Тасование массива TList
Каким
Листинг 5.2. Простое тасование элементов
procedure TDSimpleListShuffie(aList : TList;
aStart, aEnd : integer);
var
Range : integer;
Inx : integer;
Randomlnx : integer;
TempPtr : pointer;
begin
TDValidateListRange(aList, aStart, aEnd, 'TDSimpleListShuffle');
Range := succ(aEnd - aStart);
for Inx := aStart to aEnd do
begin
Randomlnx := aStart + Random (Range);
TempPtr := aList.List^[Inx];
aList.List^[Inx] := aList.List^[RandomInx];
aList.List^[RandomInx] := TempPtr;
end;
end;
А теперь давайте попробуем определить, сколько последовательностей можно получить с помощью приведенного алгоритма. После первого выполнения цикла мы получим одну из n возможных комбинаций (первый элемент может быть переставлен с любым другим, включая самого себя). После второго выполнения цикла мы снова получим одну из n возможных комбинаций, которые совместно с n комбинациями после первого выполнения дадут n(^2^) возможных комбинаций. Очевидно, что после выполнения всего цикла мы получим одну из n(^n^) возможных комбинаций.
С описанным алгоритмом связана только одна проблема. Если рассматривать тасование с другой точки зрения, с позиции главных принципов, можно показать, что для первой позиции можно выбрать один из 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) и т.д., пока не дойдете до первой и второй карты. После первого прохода по всей колоде туз окажется на первой позиции. Фактически когда вы "зацепились" за туз он "выплыл" на первую позицию. Теперь вернитесь к двенадцатой и тринадцатой картам. Выполните описанный выше процесс, на этот раз остановившись на второй и третьей картах. Обратите внимание, что вам удалось переместить двойку на вторую позицию. Продолжайте процесс сортировки, уменьшая с каждым новым циклом количество просматриваемых карт и поступая так до тех пор, пока вся колода не будет отсортирована.