Для самого общего случая сформулируем задачу сортировки та-
ким образом: имеется некоторое неупорядоченное входное множество
ключей и должны получить выходное множество тех же ключей, упоря-
доченных по возрастанию или убыванию в численном или лексикогра-
фическом порядке.
Из всех задач программирования сортировка, возможно, имеет
самый богатый выбор алгоритмов решения. Назовем некоторые факто-
ры, которые влияют на выбор алгоритма (помимо порядка алгоритма).
1). Имеющийся ресурс памяти: должны ли входное и выходное
множества располагаться в разных областях памяти или выходное
множество может быть сформировано на месте входного. В последнем
случае имеющаяся область памяти должна в ходе сортировки динами-
чески перераспределяться между входным и выходным множествами;
для одних алгоритмов это связано с большими затратами, для других
- с меньшими.
2). Исходная упорядоченность входного множества: во входном
множестве (даже если оно сгенерировано датчиком случайных вели-
чин) могут попадаться упорядоченные участки. В предельном случае
входное множество может оказаться уже упорядоченным. Одни алго-
ритмы не учитывают исходной упорядоченности и требуют одного и
того же времени для сортировки любого (в том числе и уже упорядо-
ченного) множества данного объема, другие выполняются тем быст-
рее, чем лучше упорядоченность на входе.
3). Временные характеристики операций: при определении по-
рядка алгоритма время выполнения считается обычно пропорциональ-
ным числу сравнений ключей. Ясно, однако, что сравнение числовых
ключей выполняется быстрее, чем строковых, операции пересылки,
характерные для некоторых алгоритмов, выполняются тем быстрее,
чем меньше объем записи, и т.п. В зависимости от характеристик
записи таблицы может быть выбран алгоритм, обеспечивающий миними-
зацию числа тех или иных операций.
4). Сложность алгоритма является не последним соображением
при его выборе. Простой алгоритм требует меньшего времени для его
реализации и вероятность ошибки в реализации его меньше. При про-
мышленном изготовлении программного продукта требования соблюде-
ния сроков разработки и надежности продукта могут даже превалиро-
вать над требованиями эффективности функционирования.
Разнообразие алгоритмов сортировки требует некоторой их
классификации. Выбран один из применяемых для классификации под-
ходов, ориентированный прежде всего на логические характеристики
применяемых алгоритмов. Согласно этому подходу любой алгоритм
сортировки использует одну из следующих четырех стратегий (или их
комбинацию).
1). Стратегия выборки. Из входного множества выбирается сле-
дующий по критерию упорядоченности элемент и включается в выход-
ное множество на место, следующее по номеру.
2). Стратегия включения. Из входного множества выбирается
следующий по номеру элемент и включается в выходное множество на
то место, которое он должен занимать в соответствии с критерием
упорядоченности.
3). Стратегия распределения. Входное множество разбивается
на ряд подмножеств (возможно, меньшего объема) и сортировка ве-
дется внутри каждого такого подмножества.
4). Стратегия слияния. Выходное множество получается путем
слияния маленьких упорядоченных подмножеств.
Далее приводится обзор (далеко не полный) методов сортиров-
ки, сгруппированных по стратегиям, применяемым в их алгоритмах.
Все алгоритмы рассмотрены для случая упорядочения по возрастанию
ключей.