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

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

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

Содержание 1 Оценка алгоритма сортировки 2 Классификация алгоритмов сортировки 3 Список алгоритмов сортировки 3.1 Алгоритмы устойчивой сортировки 3.2 Алгоритмы неустойчивой сортировки 3.3 Непрактичные алгоритмы сортировки 3.4 Алгоритмы, не основанные на сравнениях 3.5 Остальные алгоритмы сортировки 4 См. также 5 Литература 6 Ссылки

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

Алгоритмы сортировки оцениваются по скорости выполнения и эффективности использования памяти:

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

[править] Классификация алгоритмов сортировки

• Устойчивость (stability) — устойчивая сортировка не меняет взаимного расположения равных элементов.
• Естественность поведения — эффективность метода при обработке уже упорядоченных, или частично упорядоченных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.

• Использование операции сравнения. Алгоритмы, использующие для сортировки сравнение элементов между собой, называются основанными на сравнениях. Минимальная трудоемкость худшего случая для этих алгоритмов составляет O(n*log(n)), но они отличаются гибкостью применения. Для специальных случаев (типов данных) существуют более эффективные алгоритмы.

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

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

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

В этой таблице 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) дополнительной памяти (рассмотрено 3 варианта)
• Сортировка слиянием (Merge sort) — Сложность алгоритма: O(n log n); требуется O(n) дополнительной памяти; выстраиваем первую и вторую половину списка отдельно, а затем — сливаем упорядоченные списки
• In-place merge sort — Сложность алгоритма: O(n²), O(n log² n) или O(n log n) в зависимости от применяемого алгоритма слияния.
• Двоичное дерево сортировки (Binary tree sort) — Сложность алгоритма: O(n log n); требуется O(n) дополнительной памяти
• Цифровая сортировка (Сортировка по отделениям, Pigeonhole sort) — Сложность алгоритма: O(n+k); требуется O(k) дополнительной памяти
• Гномья сортировка (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), сочетание быстрой и пирамидальной сортировки. Пирамидальная сортировка применяется в случае, если глубина рекурсии превышает log(n).
• Patience sorting — Сложность алгоритма: O(n log n + k) — наихудший случай, требует дополнительно O(n + k) памяти, также находит самую длинную увеличивающуюся подпоследовательность
• Обменная поразрядная сортировка — Сложность алгоритма: O(n·k); требуется O(k) дополнительной памяти

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

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

[править] Алгоритмы, не основанные на сравнениях

• Блочная сортировка (Корзинная сортировка, Bucket sort)
• Лексикографичкская или поразрядная сортировка (Radix sort)
• Сортировка подсчётом (Counting sort)

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

• Топологическая сортировка
• Внешняя сортировка

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

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

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

• Дональд Кнут Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — С. 824. — ISBN 0-201-89685-0
• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1

[править] Ссылки

• Алгоритмы сортировки на algolist.manual.ru
• Анимированное сравнение алгоритмов сортировки (англ.)