3.1. ЗАДАЧА СОРТИРОВКИ

Определение. Частичным порядком на множестве называется такое двухместное отношение что для любых и с из

Примеры частичных порядков — отношение множестве целых чисел и отношение (включение множеств).

Линейным, или полным, порядком на множестве называется такой частичный порядок на что для любых двух элементов выполняется либо либо

Отношение множестве целых чисел является линейным порядком, а включение множеств нет.

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

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

Внутренняя сортировка важна как для разработки алгоритмов, так и для коммерческих приложений. В тех случаях, когда сортировка возникает как часть другого алгоритма, число сортируемых элементов обычно мало, и они помещаются в оперативную память. Тем не менее мы будем предполагать, что элементов, подлежащих сортировке, довольно много. Если же надо упорядочить только горстку элементов, то гораздо выгоднее простая стратегия вроде "сортировки взбалтыванием" со сложностью (упр. 3.5).

Известно много алгоритмов сортировки. Мы не пытаемся охватить даже все те из них, которые считаются важными; скорее мы

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