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

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

Алгоритмы сортировки являются одним из наиболее изученных направлений теории вычислительных систем. В общем случае определить характеристики выполнения сортировки достаточно просто. Можно доказать, что любой алгоритм сортировки, основанный на сравнении, принадлежит к классу O(n log(n)). Ниже мы рассмотрим несколько таких алгоритмов.

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

Коды для основных алгоритмов сортировки, описанных в этой главе, можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDSorts.pas.

Перед тем, как приступить к подробному рассмотрению алгоритмов, давайте введем несколько фундаментальных правил. Все типы сортировок, которые будут описаны ниже, используют сравнение. Чтобы алгоритм "знал", как располагать элементы в списке, их необходимо сравнивать между собой. Мы не будем приводить примеры сортировки для целых чисел, строк или переменных типа TMyRecord. Давайте рассматривать проблему сортировки более широко. Примем, что необходимо выполнить сортировку элементов, которые заданы указателями. Это тот же принцип, который мы использовали при изучении структур данных: данные задаются их указателями. Отделяя данные от манипулирования ими, мы уделяем больше внимания характеристикам алгоритмов или структур данных, а не занимаемся ненужной разработкой или оптимизацией методов для целых чисел, строк или других типов данных.

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