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

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

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

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

применимы к данным, находящимся на внешних устройствах памяти, и имеют огромное коммерческое значение.

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

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