Внутренняя сортировка

Существует, по крайней мере, пять широко известных способов, применяемых в алгоритмах внутренней сортировки.

1. Вставка. На i-м этапе i-е имя помещается на надлежащее место c i-1 уже отсортированными именами.

2. Обмен. Два имени, расположение которых не соответствует порядку, меняются местами (обмен). Эта процедура повторяется, пока существуют такие пары.

3. Выбор. На i-м этапе из неотсортированных имен выбирается i-е наибольшее (наименьшее) имя и помещается на соответствующее место.

4. Распределение. Имена распределяются по группам, и содержимое групп затем объединяется таким образом, чтобы частично отсортировать таблицу; процесс повторяется до тех пор, пока таблица не будет отсортирована полностью.

5. Слияние. Таблица делится на подтаблицы, которые сортируются по отдельности и затем сливаются в одну.

Эти классы нельзя назвать ни взаимоисключающими, ни исчерпывающими. Они

удобны для классификации алгоритмов сортировки. В рассматриваемых алгоритмах имена образуют последовательность x₁, …, x_n. Значением x_i является любое текущее имя i позиции последовательности. В каждом из рассматриваемых алгоритмов будем считать, что имена нужно сортировать на месте, т.е. перемещение имен должно происходить внутри последовательности x₁, …, x_n. При этом существует одна или две дополнительные ячейки, в которых временно размещается значение имени.

Ограничение «сортировка на месте» основано на предположении, что число имен настолько велико, что во время сортировки не допускается перенос их в другую область памяти.

3.2. Сравнение эффективности алгоритмов сортировки

Чтобы получить некоторое представление об ожидаемой эффективности, рассмотрим задачу сортировки с теоретической точки зрения.

Один из способов оценки эффективности алгоритмов сортировки состоит в подсчете числа сравнений имен ‘x_i: x_j’ за время сортировки. Эта характеристика не всегда является определяющей, но для большинства алгоритмов она является хорошей мерой производимой работы. Будем рассматривать алгоритмы, основанные на абстрактном линейном упорядочении пространства имен: для любой пары имен x_i, x_j при i ¹ j либо x_i < x_j, либо x_i > x_j.

Любой такой алгоритм можно представить в виде расширенного бинарного дерева решений, в котором каждый внутренний узел соответствует сравнению имен, и каждый лист (внешний узел) — исходу алгоритма. Это дерево можно рассматривать как блок-схему алгоритма сортировки, в котором все циклы «размотаны» и показаны только сравнения имен.

Пример. Рассмотрим сортировку элементов массива {x₁, x₂, x₃} с использованием бинарного дерева.

Рис. 3.3. Бинарное дерево решений для сортировки трех имен

В любом таком дереве решений каждая перестановка определяет единственный путь от корня к листу. Листья, соответствующие разным перестановкам, должны быть разными. Тогда ясно, что в дереве решений для сортировки n имен должно быть по крайней мере n! листьев (n! — количество перестановок из n).

Заметим, что высота дерева решений h равна числу сравнений, требующихся алгоритму в наихудшем случае.

Поскольку бинарное дерево высоты h может иметь не больше 2^h листьев, заключаем что

т.к.

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

Длина внешних путей дерева решений равна сумме всех расстояний от корня до листьев, деление ее на n! дает среднее число сравнений для соответствующего алгоритма.