На этом шаге мы рассмотрим некоторые алгоритмы сортировки.
Алгоритмы сортировки являются частным случаем перестановочных алгоритмов, поскольку они тоже изменяют порядок следования элементов. Тем не менее сортировка является более сложной операцией и обычно занимает больше времени, чем простые перестановки. На практике эти алгоритмы обычно имеют сложность выше линейной и требуют поддержки итераторов произвольного доступа (для приемника). Алгоритмы сортировки перечислены в таблице 1.
| Название | Описание |
|---|---|
| sort() | Сортирует все элементы |
| stable_sort() | Сортирует с сохранением порядка следования равных элементов |
| partial_sort() | Сортирует до тех пор, пока первые n элементов не будут упорядочены правильно |
| nth_element() | Сортирует элементы слева и справа от элемента в позиции n |
| partition() | Изменяет порядок следования элементов так, что элементы, соответствующие критерию, оказываются спереди |
| stable_partition() | To же, что и partition(), но с сохранением относительного расположения элементов, соответствующих и не соответствующих критерию |
| make_heap() | Преобразует интервал в кучу |
| push_heap() | Добавляет элемент в кучу |
| рор_hеар() | Удаляет элемент из кучи |
| sort_heap() | Сортирует кучу (которая после вызова перестает быть кучей) |
Алгоритмы сортировки часто критичны по времени, поэтому стандартная библиотека C++ содержит несколько алгоритмов, различающихся по способу сортировки или составу сортируемых элементов (полная/частичная сортировка). Например, алгоритм nth_element() прекращает работу, когда n-й элемент последовательности занимает правильное место в соответствии с критерием сортировки. Для остальных элементов он гарантирует только то, что предшествующие элементы имеют меньшее либо равное, а последующие элементы - большее либо равное значение. Сортировка всех элементов осуществляется перечисленными ниже алгоритмами.
- sort(). Исторически этот алгоритм основан на механизме быстрой сортировки, гарантирующем хорошую
среднестатистическую сложность (n*log(n)), но очень плохую (квадратичную) сложность в худшем случае:
// Сортировка всех элементов // - средняя сложность n*log(n) // - квадратичная сложность n*n в худшем случае sort (coll.begin(), coll.end());
Если в вашей ситуации очень важно избежать худших случаев, воспользуйтесь другим алгоритмом, например partial_sort() или stable_sort().
- partial_sort(). Исторически этот алгоритм основан на механизме сортировки в куче (heapsort),
гарантирующем сложность n*log(n) в любом случае. Тем не менее обычно сортировка в куче выполняется в
2-5 раз медленнее быстрой сортировки. Итак, с учетом реализаций sort() и partial_sort(), алгоритм
partial_sort() лучше по сложности, но по скорости работы sort() обычно превосходит его.
Преимущество алгоритма partial_sort() заключается в том, что сложность n*log(n) гарантирована и
никогда не ухудшается до квадратичной сложности.
Алгоритм partial_sort() также обладает особым свойством: он прекращает сортировку, когда требуется отсортировать только n первых элементов. Чтобы отсортировать все элементы, передайте конец последовательности во втором и в последнем аргументах:
// Сортировка всех элементов // - всегда сложность n*log(n) // - но обычно работает вдвое медленнее sort()*/ partial_sort (coll.begin(), coll.end(), coll.end());
- stable_sort(). Исторически этот алгоритм основан на механизме сортировки со слиянием. Он сортирует
все элементы переданного интервала:
// Сортировка всех элементов // - сложность n*log(n) или n*log(n)*log(n) stable_sort (coll.begin(),coll.end());
Для достижения сложности n*log(n) необходима дополнительная память, в противном случае алгоритм выполняется со сложностью n*log(n)*log(n). Достоинством stable_sort() является сохранение порядка следования равных элементов.
Итак, теперь вы приблизительно представляете, какой алгоритм лучше всего подходит для ваших целей, однако это не все. Стандарт гарантирует лишь сложность, но не реализацию алгоритма. Это сделано для того, чтобы проектировщики могли использовать новые разработки в области алгоритмов и совершенствовать реализации без нарушения стандартов. Например, алгоритм sort() в реализации STL от SGI использует механизм интроспективной сортировки - новый алгоритм, который по умолчанию работает как быстрая сортировка, но в случаях с квадратичной сложностью переключается на сортировку в куче. Впрочем, у того факта, что стандарт не диктует реализацию алгоритма, есть и недостаток - можно реализовать очень плохой алгоритм, который соответствует стандарту. Например, реализация sort() на базе сортировки в куче будет считаться соответствующей стандарту. Конечно, оптимальный алгоритм можно выбрать на основании тестирования, однако нельзя гарантировать, что программный код хронометража будет работать на других платформах.
На следующем шаге мы закончим изучение этого вопроса.
