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

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

Глава 5. Сортировка

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

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

Алгоритмы сортировки

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

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

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

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

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

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

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

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

procedure TDValidateListRange(aList : TList;