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

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

Во‑вторых, многие алгоритмы сортировки являются интересными примерами программирования. Они демонстрируют важные методы, такие как частичное упорядочение, рекурсия, слияние списков и хранение двоичных деревьев в массиве.

Наконец, сортировка является одной из немногих задач с точными теоретическими ограничениями производительности. Можно показать, что время выполнения любого алгоритма сортировки, который использует сравнения, составляет порядка O(N * log(N)). Некоторые алгоритмы достигают теоретического предела, то есть они являются оптимальными в этом смысле. Есть даже ряд несколько алгоритмов, которые используют другие методы вместо сравнений, которые выполняются быстрее, чем за время порядка O(N * log(N)).

Общие соображения

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

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

Таблицы указателей

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

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

Type Emloyee

ID As Integer

LastName As String

FirstName As String

<и т.д.>

End Type

‘ Выделить память под записи.

Dim EmloyeeData(1 To 10000)

Чтобы отсортировать сотрудников по идентификационному номеру, нужно создать таблицу индексов, которая содержит индексы и значения ID values из записей. Индекс элемента показывает, какая запись в массиве EmployeeData содержит соответствующие данные.

Type IdIndex

ID As Integer

Index As Integer

End Type

‘ Таблица индексов.

Dim IdIndexData(1 To 10000)

Проинициализируем таблицу индексов так, чтобы первый индекс указывал на первую запись данных, второй — на вторую, и т.д.

For i = 1 To 10000

IdIndexData(i).ID = EmployeeData(i).ID

IdIndexData(i).Index = i

Next i

Затем, отсортируем таблицу индексов по идентификационному номеру ID. После этого, поле Index в каждом элементе IdIndexData указывает на соответствующую запись данных. Например, первая запись в отсортированном списке — это EmployeeData(IdIndexData(1).Index).

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

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