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