Классификация методов сортировки.

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

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

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

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

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

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

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

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

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

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

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

Рис.1.1. Общая классификация методов сортировки.

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