Общие сведения и некоторые определения

Термин «сортировка» (sorting) определяется как «распределение, отбор по сортам или деление на категории, сорта, разряды». В общем случае сортировку следует понимать как процесс перегруппировки заданного множества объектов в некотором определенном порядке. Цель сортировки – облегчить последующий поиск элементов в таком упорядоченном (отсортированном) множестве. Это почти универсальная, фундаментальная деятельность. Мы встречаемся с отсортированными объектами в телефонных справочниках, в библиотеках, в словарях, на складах – почти везде, где нужно искать хранимые объекты. Даже малышей учат держать свои вещи «в порядке», и они уже сталкиваются с некоторыми видами сортировок задолго до того, как познакомятся с азами арифметики. С точки зрения обработки данных сортировка (упорядочение) таблиц позволяет существенно ускорить процесс поиска данных, о чем свидетельствует материал раздела 10.

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

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

Введем некоторые понятия и обозначения. Если у нас есть элементы

a[0], a[1], a[2], …, a[HighIndex],

то сортировка есть перестановка этих элементов в последовательность

a[k₀], a[k₁], …, a[k_HighIndex] = a¢[0], a¢[1], …, a¢[HighIndex],

такую, что при некоторой упорядочивающей функции f выполняются отношения

f(a¢[0])£ f(a¢[1]) £ … £ f(a¢[HighIndex]).

где символом « £ » обозначено отношение «предшествования», задающее некоторое правило упорядочения.

Обычно упорядочивающая функция не вычисляется по какому-либо правилу, а хранится как явная компонента, ассоциированная с каждым элементом сортируемой таблицы. Эта компонента является полем ключа или, просто, ключом элемента данных. Как и ранее, в разделе 11, ограничимся описанием элемента таблицы и самой таблицы a в форме (10.1) и (10.2).

Если в результате сортировки элементы таблицы располагаются в соответствии с соотношением (10.3) или (10.4), то говорят, что таблица упорядочена по возрастанию (значений ключа Кey). Если после сортировки элементы располагаются так, что значения ключа уменьшаются при увеличении индекса, то выполнено упорядочение по убыванию. В дальнейшем везде будем считать, что сортировки производят упорядочение элементов по возрастанию ключа.

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