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

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

Поскольку фактически будет выполняться сравнение указателей, имеет смысл использовать структуры данных, которые хранят элементы в форме указателей. Для начала рассмотрим алгоритм сортировки на примере стандартного массива TList. Написанные нами функции сортировки могут быть обобщенными: они будут перегруппировывать и сравнивать указатели с использованием функции сравнения, заданной пользователем. Затем обобщенные функции сортировки можно будет преобразовать с целью применения с другими типами массивов. После описания стандартных алгоритмов сортировки мы рассмотрим сортировку в связных списках. Таким образом, большинство написанных функций сортировки в качестве входного параметра смогут принимать экземпляр TList.

И, наконец, для создания действительно обобщенных функций, мы введем возможность сортировки не только всего массива TList, но и некоторого его диапазона. Для описания диапазона будут использоваться два параметра: индекс первого элемента диапазона и индекс последнего элемента диапазона. Это подразумевает, что функция сортировки должна выполнять проверку попадания индекса первого и последнего элемента сортируемого диапазона в диапазон допустимых индексов массива TList (т.е. оба индекса больше или равны нулю и меньше, чем Count, и первый индекс меньше второго).

Листинг 5.1. Проверка попадания индекса в допустимый диапазон индексов для массива TList

procedure TDValidateListRange(aList : TList;

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? Большинство из вас в качестве первого алгоритма приведут самый простой: посетить каждый элемент массива, от первого до последнего, и переставить его с другим, случайно выбранным элементом. Реализация такого алгоритма в 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^) возможных комбинаций.