Оценка алгоритмов сортировки

Существует много различных алгоритмов сортировки. Все они имеют свои положительные стороны, но общие критерии оценки алгоритма сортировки таковы:

• Насколько быстро данный алгоритм сортирует информацию в среднем?
• Насколько быстро он работает в лучшем и худшем случаях?
• Естественно или неестественно он себя ведет?
• Переставляет ли он элементы с одинаковыми ключами?^[1]

Давайте подробнее рассмотрим эти критерии. Очевидно, что скорость работы любого алгоритма сортировки имеет большое значение. Скорость сортировки^[2] массива непосредственно связана с количеством сравнений и количеством обменов, происходящих во время сортировки, причем обмены занимают больше времени. Сравнение происходит тогда, когда один элемент массива сравнивается с другим; обмен происходит тогда, когда два элемента меняются местами. Время работы одних алгоритмов сортировки растет экспоненциально, а время работы других логарифмически зависит от количества элементов.

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

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

Чтобы понять, почему переупорядочивание элементов с одинаковыми ключами имеет определенное значение, представьте себе базу данных почтовой рассылки, упорядоченную по главному ключу и подключу. Главным ключом является почтовый индекс, а в пределах одного почтового индекса записи упорядочены по фамилии. При добавлении в список нового адреса и пересортировке списка порядок подключей (то есть фамилий внутри почтовых индексов) не должен меняться. Для гарантии, что это не произойдет, алгоритм сортировки не должен обменивать ключи с одинаковым значением^[3].

Далее будут представлены характерные для каждой группы алгоритмы сортировка с анализом эффективности. После них будут продемонстрированы более совершенные методы сортировки.

^[1]Если в отсортированном массиве элементы с одинаковыми ключами идут в том же порядке, в котором они располагались в исходном массиве, то алгоритм сортировки называется устойчивым, а в противном случае — неустойчивым.

^[2]Синонимы: быстродействие, эффективность.

^[3]Т.е. должен быть устойчивым.