Сортировки

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

Сформулируем задачу сортировки.

Вход: последовательность n чисел (a ₁; a ₂;…; a_n).

Выход: Перестановка (a` <sub>1</sub>; a` ₂;…; a`<sub>n</sub>) исходной последовательности, для которой a` ₁ ≤ a` <sub>2</sub> ≤…≤ a`_n.

Например, получив на вход последовательность(21, 43, 37, 18, 32), алгоритм сортировки должен выдавать на выход (18, 21, 32, 37, 43).

Свойства и классификация

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

По сфере применения сортировки делят на следующие группы:

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

Также алгоритмы классифицируются по:

• потребности в дополнительной памяти или её отсутствию
• потребности в знаниях о структуре данных, выходящих за рамки операции сравнения, или отсутствию таковой

Рассмотрим основные сортировки:

Сортировка выбором (Selection sort). Может быть реализован и как устойчивый и как неустойчивый алгоритм. На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае Θ(n ²), предполагая что сравнения делаются за постоянное время.

Шаги алгоритма:

1. находим номер минимального значения в текущем списке

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

3. теперь сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы

Так как после каждого прохода по внутреннему циклу делается только один обмен, то общее число обменов равно N-1, что в N/2 раз меньше, чем в сортировке пузырьком.

Число проходов по внутреннему циклу равно N-1 даже в случае сортировки частично или полностью отсортированного массива.

Наихудший случай:

Число сравнений в теле цикла равно (N-1)*N/2.

Число сравнений в заголовках циклов (N-1)*N/2.

Число сравнений перед операцией обмена N-1.

Суммарное число сравнений N²−1.

Число обменов N-1.

Сортировка простыми обменами, сортиро́вка пузырько́м (bubble sort). Сложность алгоритма: O(n ²).

Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим наибольшим элементом, а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма).

Наихудший случай:

• Число сравнений в теле цикла равно (N-1)*N/2.
• Число сравнений в заголовках циклов (N-1)*N/2.
• Суммарное число сравнений равно (N-1)*N.
• Число присваиваний в заголовках циклов равно (N-1)*N/2.
• Число обменов равно (N-1)*N/2.

Наилучший случай:

• Число сравнений в теле цикла равно (N-1).
• Число сравнений в заголовках циклов (N-1).
• Суммарное число сравнений равно 2*(N-1).
• Число обменов равно 0.

Дата добавления: 2014-01-05