Алгоритм сортировки

Материал из Википедии — свободной энциклопедии

Алгоритм сортировки — это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле по которому производится сортировка называется ключом сортировки. На практике, в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма.

Пожалуй, никакая другая проблема не породила такого количества разнообразнейших решений, как задача сортировки. Существует ли некий «универсальный», наилучший алгоритм? Вообще говоря, нет. Однако, имея приблизительные характеристики входных данных, можно подобрать метод, работающий оптимальным образом.

[править] Оценка алгоритма сортировки

Для того, чтобы обоснованно сделать такой выбор, рассмотрим параметры, по которым будет производиться оценка алгоритмов.

Время сортировки — основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для сортировки важны худшее, среднее и лучшее поведение алгоритма в терминах размера списка (n). Для типичного алгоритма хорошее поведение — это O(n log n) и плохое поведение — это Ω(n²). Идеальное поведение для сортировки — O(n). Алгоритмы сортировки, которые используют только абстрактную операцию сравнения ключей всегда нуждаются по меньшей мере в Ω(n log n) сравнениях в среднем;
Память — ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. При оценке используемой памяти не будет учитываться место, которое занимает исходный массив и независящие от входной последовательности затраты, например, на хранение кода программы.
Устойчивость (stability) — устойчивая сортировка не меняет взаимного расположения равных элементов. Такое свойство может быть очень полезным, если они состоят из нескольких полей, а сортировка происходит по одному из них.
Естественность поведения — эффективность метода при обработке уже отсортированных, или частично отсортированных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.

Ещё одним важным свойством алгоритма является его сфера применения. Здесь основных типов сортировки две:

Внутренняя сортировка оперирует с массивами, целиком помещающимися в оперативной памяти с произвольным доступом к любой ячейке. Данные обычно сортируются на том же месте, без дополнительных затрат.
Внешняя сортировка оперирует с запоминающими устройствами большого объёма, но с доступом не произвольным, а последовательным (сортировка файлов), т.е в данный момент мы 'видим' только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Это накладывает некоторые дополнительные ограничения на алгоритм и приводит к специальным методам сортировки, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным на носителе производится намного медленнее, чем операции с оперативной памятью.
- доступ к носителю осуществляется последовательным образом: в каждый момент времени можно считать или записать только элемент, следующий за текущим
- объём данных не позволяет им разместиться в ОЗУ

[править] Список алгоритмов сортировки

В этой таблице n — это количество записей, которые необходимо отсортировать, а k — это количество уникальных ключей.

[править] Алгоритмы устойчивой сортировки

Сортировка пузырьком (англ. Bubble sort ) — сложность алгоритма: O(n²); для каждой пары индексов производится обмен, если элементы расположены не по порядку
Сортировка перемешиванием (Сортировка коктейлем, Cocktail sort, bidirectional bubble sort) — Сложность алгоритма: O(n²)
Сортировка методом вставок (Insertion sort) — Сложность алгоритма: O(n²); определяем где текущий элемент должен находится в отсортированном списке и вставляем его туда
Блочная сортировка (Корзинная сортировка, Bucket sort) — Сложность алгоритма: O(n); требуется O(k) дополнительной памяти
Сортировка подсчётом (Counting sort) — Сложность алгоритма: O(n+k); требуется O(n+k) дополнительной памяти
Сортировка слиянием (Merge sort) — Сложность алгоритма: O(n log n); требуется O(n) дополнительной памяти; сортируем первую и вторую половину списка отдельно, а затем — сливаем отсортированные списки
In-place merge sort — Сложность алгоритма: O(n²)
Двоичное дерево сортировки (Binary tree sort) — Сложность алгоритма: O(n log n); требуется O(n) дополнительной памяти
Цифровая сортировка (Сортировка по отделениям, Pigeonhole sort) — Сложность алгоритма: O(n+k); требуется O(k) дополнительной памяти
Поразрядная сортировка (Radix sort) — Сложность алгоритма: O(n·k); требуется O(n) дополнительной памяти

сортирует строки буква за буквой

Гномья сортировка (Gnome sort) — Сложность алгоритма: O(n²)

[править] Алгоритмы неустойчивой сортировки

Сортировка методом выбора (Selection sort) — Сложность алгоритма: O(n²); поиск наименьшего или наибольшего элемента и помещения его в начало или конец отсортированного списка
Сортировка методом Шелла (Shell sort) — Сложность алгоритма: O(n log n); попытка улучшить сортировку вставками
Сортировка расчёской (Comb sort) — Сложность алгоритма: O(n log n)
Пирамидальная сортировка (Сортировка кучи, Heapsort) — Сложность алгоритма: O(n log n); превращаем список в кучу, берём наибольший элемент и добавляем его в конец списка
Плавная сортировка (Smoothsort) — Сложность алгоритма: O(n log n)
Быстрая сортировка (Quicksort) — Сложность алгоритма: O(n log n) — среднее время, O(n²) — худший случай; широко известен как быстрейший из известных для сортировки больших случайных списков; с разбиением исходного набора данных на две половины так, что любой элемент первой половины упорядочен относительно любого элемента второй половины; затем алгоритм применяется рекурсивно к каждой половине
Introsort — Сложность алгоритма: O(n log n)
Patience sorting — Сложность алгоритма: O(n log n + k) — наихудший случай, требует дополнительно O(n + k) памяти, также находит самую длинную увеличивающуюся подпоследовательность

[править] Непрактичные алгоритмы сортировки

Алгоритм Bogosort — O(n × n!) — среднее время, неограниченный худший случай.
Глупая сортировка (Stupid sort) — O(n³); рекурсивная версия требует дополнительно O(n²) памяти
Bead Sort — O(n) or O(√n), требуется специализированное железо
Блинная сортировка (Pancake sorting) — O(n), требуется специализированное железо

[править] Остальные алгоритмы сортировки

Топологическая сортировка

[править] См. также

O-большое
Временная сложность алгоритма
Ёмкостная сложность алгоритма
Внешняя сортировка
Сортирующие сети (сравнение)
Сравнивание
Трансформация Шварца

[править] Литература

Кнут Д. Искусство программирования, том 3. Сортировка и поиск, 2-е издание (Вильямс, 2000, ISBN 5-8459-0082-4)
Алгоритмы: построение и анализ,2 издание. Томаса Х. Кормена, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн (Вильямс, 2005, ISBN 5-8459-0857-4)

http://www.williamspublishing.com/Books/5-8459-0857-4.html