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

Можно ли каким-то образом устранить двойную проверку индексов? К счастью, это так. Класс TList имеет еще одно свойство - List. Это свойство, доступное только для чтения, возвращает указатель типа PPointerList на внутренний массив указателей, используемый массивом TList для хранения элементов. Никакие вспомогательные методы не вызываются и никаких проверок не производится. Конечно, применяя это свойство, мы принимаем на себя ответственность, что при попытках чтения и записи мы не должны выходить за границы массива.

Принимая во внимание все вышесказанное, можно объявить функцию сортировки следующего вида:

Туре

TtdSortRoutine =procedure(aList : TList;

aFirst, aLast : integer;

aCompare : TtdCompareFunc)

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

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

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

Кроме того, есть еще одна последовательность данных, которую можно использовать при тестировании алгоритмов сортировки, - набор данных, содержащий большое количество повторений ограниченного количества элементов. Другими словами, в таком наборе находятся элементы, для многих из которых функция сравнения будет возвращать значение 0. Это немного странно, но есть, по крайней мере, один алгоритм сортировки, который традиционно плохо работает с наборами данных с повторениями элементов.

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

Каким образом можно перетасовать элементы массива TList? Большинство из вас в качестве первого алгоритма приведут самый простой: посетить каждый элемент массива, от первого до последнего, и переставить его с другим, случайно выбранным элементом. Реализация такого алгоритма в Delphi будет выглядеть следующим образом:

Листинг 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.)