Упорядочить последовательность

Сортировка относится к алгоритмам обработки таблиц (массивов) любого типа. Смысл этой задачи заключается в перестановке элементов таблицы в определенном порядке. Отсортировать числовую таблицу - это значит переставить вней элементы так, чтобы они расположились в порядке убывания (возрастания) значений с возрастанием номера элемента.

Пример 1.

Пример 2.

Здесь индексы показывают относительный порядок элементов с равными значениями.

Сортировка таблицы литерного типа обычно заключается в упорядочении значений по алфавиту.

Пример 3.

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

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

Известные алгоритмы сортировки данных, расположенных в оперативной памяти, чрезвычайно разнообразны. Их анализ очень полезен с точки зрения обучения, так как в них используются практически все универсальные приемы конструирования алгоритмов любой сложности. По словам Н. Вирта, " создается впечатление, что можно построить целый курс программирования, выбирая примеры только из задач сортировки". Интересен этот класс алгоритмов еще и тем, что на нем наглядно демонстрируются богатейшие возможности программирования: насколько разными путями можно прийти к одной цели - получению упорядоченной таблицы! На множестве алгоритмов сортировки становится понятной необходимость оценки качества алгоритма, критериями которого являются экономия памяти и увеличение быстродействия.

В настоящей статье рассматриваются три наиболее простых способа сортировки. На Рис. 2 их поясняют: последовательность разновысоких треугольников - метод вставок; прямоугольников - метод выбора; " пузырьки, всплывающие в резервуаре" - метод обмена. Несмотря на свою внешнюю несложность и очевидность, они интересны тем, что практически все другие возможности упорядочения являются производными этих трех. Эти методы выбраны также и по соображениям эффективности алгоритмов в смысле экономии памяти. Они позволяют переупорядочить таблицу, не прибегая к вспомогательной таблице, правда, первоначальный вид таблицы после обработки ее такими алгоритмами теряется. Что касается быстродействия этих алгоритмов, то для небольших учебных таблиц оно примерно одинаково.

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

Для сохранения общности изложения рассматриваются алгоритмы упорядочения исходной последовательности A₁, A₂,..., A_N по возрастанию. Переход к алгоритмам упорядочения по убыванию не представляет труда.