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

aStart, aEnd : integer; aMessage : string);

begin

if (aList = nil) then

raise EtdTListException.Create(Format(LoadStr(tdeTListlsNil), [aMessage]));

if (aStart < 0) or (aStart >= aList.Count) or

(aEnd < 0) or (aEnd >= aList.Count) or (aStart > aEnd) then

raise EtdTListException.Create(Format(LoadStr(tdeTListInvalidRange),

[aStart, aEnd, aMessage]));

end;

Выполнение проверки до сортировки массива дает нам дополнительное преимущество. Стандартный метод доступа к элементам массива TList - это свойство Items. Поскольку это свойство по умолчанию, его можно опускать, т.е. вместо MyList.Items[i] записывать MyList[i]. Несмотря на кажущуюся простоту, здесь скрыта большая проблема, по крайней мере, если говорить об эффективности сортировки. Дело в том, что, например, оператор MyList [i] приводит к тому, что компилятор вместо вызова элемента вставляет метод MyList.Get(i) - метод записи свойства Items. И первое, что делает метод Get, - проверяет, что индекс i находится в диапазоне от 0 до Count-1. Тем не менее, если мы реализовали алгоритм сортировки правильно, мы можем гарантировать, что переданный методу индекс уже находится внутри допустимого диапазона индексов массива. То же относится и к записи значения в MyList[i]: вызывается метод Put, который также проверяет попадание переданного ему индекса внутрь допустимого диапазона. Таким образом, используя свойство Items, мы выполняем ненужный объем работы: вызываем метод, который проверяет уже проверенный индекс. Не очень-то хорошо.

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

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

Туре

TtdSortRoutine =procedure(aList : TList;

aFirst, aLast : integer;

aCompare : TtdCompareFunc)

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

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

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

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

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

Тасование массива TList

Каким образом можно перетасовать элементы массива 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;