Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi
С описанным алгоритмом связана только одна проблема. Если рассматривать тасование с другой точки зрения, с позиции главных принципов, можно показать, что для первой позиции можно выбрать один из 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). По пути к правому краю колоды вы "захватили" короля и переместили его на последнюю позицию.
А теперь снова пройдите колоду справа налево до второй карты. Во вторую позицию попадет двойка. Продолжайте чередовать направления проходов до тех пор, пока не будет отсортирована вся колода.
