Классификация задач сортировки и поиска

Пусть задано некоторое множество элементов а₁ а₂, а₃, . . ., а_n и требуется выстроить эти элементы по порядку в соответствии с заданной функцией предпочтения (например, по алфавиту). Очень часто значения функции предпочтения явно хранятся в исходных элементах в виде специального ключевого поля целого или строкового типа.

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

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

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

Методы сортировки массивов можно разделить на две большие группы:

· Универсальные методы, не требующие никакой дополнительной информации об исходных данных и выполняющие сортировку “на месте”, т.е. без использования больших объемов дополнительной памяти (например – для размещения копии исходного массива); такие методы в лучшем случае дают оценку трудоемкости порядка O(n*log ₂ n)

· Специальные методы, которые либо за счет некоторой дополнительной информации об исходных данных, либо за счет использования большой дополнительной памяти позволяют получить более высокую производительность сортировки порядка O(n) (примеры – карманная и поразрядная сортировка)

В свою очередь, универсальные методы сортировки делятся на две подгруппы:

· Простейшие методы с трудоемкостью порядка O(n²): сортировка обменом, сортировка выбором и сортировка вставками

· Улучшенные методы с трудоемкостью O(n*log ₂ n): метод Шелла, пирамидальная сортировка, быстрая сортировка

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

Общая классификация методов сортировки приводится на схеме. Описание всех методов приводится далее в пособии.

Аналогично можно провести классификацию методов поиска. Прежде всего – внутренний поиск и внешний поиск. Внутренний поиск – универсальный и специальный. Универсальный – поиск в упорядоченном или неупорядоченном наборе данных. Неупорядоченный набор – метод простого перебора (массив, список, иногда – дерево), упорядоченный – метод двоичного поиска в массиве или дереве. Специальный метод поиска в массиве (хеш-поиск) предполагает особую его организацию и используется при определенных ограничениях (правда, при выполнении этих ограничений данный метод дает потрясающую производительность – одно сравнение для поиска ЛЮБОГО элемента, независимо от объема входных данных!). Внешний поиск реализуется для сверхбольших объемов данных, которые нельзя одновременно разместить в основной памяти и требует использования внешних файлов (один из самых известных методов основан на использовании так называемых B-деревьев). Универсальные методы поиска были рассмотрены ранее, а остальные рассматриваются ниже, после описания методов сортировки.