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

Вернемся к проблеме: если не брать во внимание случай, когда 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) и т.д., пока не дойдете до первой и второй карты. После первого прохода по всей колоде туз окажется на первой позиции. Фактически когда вы "зацепились" за туз он "выплыл" на первую позицию. Теперь вернитесь к двенадцатой и тринадцатой картам. Выполните описанный выше процесс, на этот раз остановившись на второй и третьей картах. Обратите внимание, что вам удалось переместить двойку на вторую позицию. Продолжайте процесс сортировки, уменьшая с каждым новым циклом количество просматриваемых карт и поступая так до тех пор, пока вся колода не будет отсортирована.