Существует много различных алгоритмов сортировки. Все они имеют свои положительные стороны, но общие критерии оценки алгоритма сортировки таковы:
- Насколько быстро данный алгоритм сортирует информацию в среднем?
- Насколько быстро он работает в лучшем и худшем случаях?
- Естественно или неестественно он себя ведет?
- Переставляет ли он элементы с одинаковыми ключами?[1]
Давайте подробнее рассмотрим эти критерии. Очевидно, что скорость работы любого алгоритма сортировки имеет большое значение. Скорость сортировки[2] массива непосредственно связана с количеством сравнений и количеством обменов, происходящих во время сортировки, причем обмены занимают больше времени. Сравнение происходит тогда, когда один элемент массива сравнивается с другим; обмен происходит тогда, когда два элемента меняются местами. Время работы одних алгоритмов сортировки растет экспоненциально, а время работы других логарифмически зависит от количества элементов.
Время работы в лучшем и худшем случаях имеет значение, если одна из этих ситуаций будет встречаться довольно часто. Алгоритм сортировки зачастую имеет хорошее среднее время выполнения, но в худшем случае он работает очень медленно.
Поведение алгоритма сортировки называется естественным, если время сортировки минимально для уже упорядоченного списка элементов, увеличивается по мере возрастания степени неупорядоченности списка и максимально, когда элементы списка расположены в обратном порядке. Объем работы алгоритма оценивается количеством производимых сравнений и обменов.
Чтобы понять, почему переупорядочивание элементов с одинаковыми ключами имеет определенное значение, представьте себе базу данных почтовой рассылки, упорядоченную по главному ключу и подключу. Главным ключом является почтовый индекс, а в пределах одного почтового индекса записи упорядочены по фамилии. При добавлении в список нового адреса и пересортировке списка порядок подключей (то есть фамилий внутри почтовых индексов) не должен меняться. Для гарантии, что это не произойдет, алгоритм сортировки не должен обменивать ключи с одинаковым значением[3].
Далее будут представлены характерные для каждой группы алгоритмы сортировка с анализом эффективности. После них будут продемонстрированы более совершенные методы сортировки.
[1]Если в отсортированном массиве элементы с одинаковыми ключами идут в том же порядке, в котором они располагались в исходном массиве, то алгоритм сортировки называется устойчивым, а в противном случае — неустойчивым.
[2]Синонимы: быстродействие, эффективность.
[3]Т.е. должен быть устойчивым.