становки их значений. В табл. 9.5 перечислены перестановочные алгоритмы стандартной библиотеки С++. Как и в случае с модифицирующими алгоритмами, их приемником не может быть ассоциативный контейнер, поскольку элементы ассоциативного контейнера считаются константными.

Таблица 9.5. Перестановочные алгоритмы

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

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

Сложность операций рассматривается на с, 37.

Алгоритмы сортировки часто критичны по времени, поэтому стандартная библиотека С++ содержит несколько алгоритмов, различающихся по способу сортировки или составу сортируемых элементов (полная/частичная сортировка). Например, алгоритм nth element() прекращает работу, когда п-й элемент последовательности занимает правильное место в соответствии с критерием сортировки. Для остальных элементов он гарантирует только то, что предшествующие элементы имеют меньшее либо равное, а последующие элементы - большее либо равное значение. Сортировка всех элементов осуществляется перечисленными ниже алгоритмами.

О sort(). Исторически этот алгоритм основан на механизме быстрой сортировки, гарантируюгдем хорошую среднестатистическую сложность (nxlog(n)), но очень плохую (квадратичную) сложность в худшем случае:

/* Сортировка всех элементов

* - средняя сложность n*log(n)

* - квадратичная сложность п*п в худшем случае */

sort (coll.beginO. coll.endO):

Если в вашей ситуации очень важно избежать худших случаев, воспользуйтесь другим алгоритмом, например partial sort() или stable sort().

О partiaLsort(). Исторически этот алгоритм основан на механизме сортировки в куче (heapsort), гарантирующем сложность nxlog(n) в .любом случае. Тем не менее обычно сортировка в куче выполняется в 2-5 раз медленнее быстрой сортировки. Итак, с учетом реализаций sort() и partial SGrt(), алгоритм partiaLsortO лучше по сложности, но по скорости работы sort() обычно превосходит его. Преимущество алгоритма partiaLsort() заключается в том, что сложность nxlog(n) гарантирована и никогда не ухудшается до квадратичной сложности.

Алгоритм partial sort() также обладает особым свойством: он прекращает сортировку, когда требуется отсортировать только п первых элементов. Чтобы отсортировать все элементы, передайте конец последовательности во втором и в последнем аргументах:

/* Сортировка всех элементов

* - всегда сложность n*log(n)

* - но обычно работает вдвое медленнее sortO

partial 5ort (coll.beginO. coll.endO. coll.endO):

О stable sort(). Исторически этот алгоритм основан на механизме сортировки со слиянием. Он сортирует все элементы переданного интервала:

/* Сортировка всех элементов

* - сложность n*log(n) или n*log(n)*log(n) */

stablejort (coll.beginO. coll.endO):

Для достижения сложности nxlog(n) необходима дополнительная память, в противном случае алгоритм выполняется со сложностью nxlog(n)xlog(n). Достоинством stable sort() является сохранение порядка следования равных элементов.

Итак, теперь вы приблизительно представляете, какой алгоритм лучше всего подходит для ваших целей, однако это не все. Стандарт гарантирует лишь сложность, но не реализацию алгоритма Это сделано для того, чтобы проектировщики могли использовать новые разработки в области алгоритмов и совершенствовать реализации без нарушения стандартов. Например, алгоритм sort() в реализации STL от SGI использует механизм интроспективной сортировки - новый алгоритм, который по умолчанию работает как быстрая сортировка, но в случаях с квадратичной сложностью переключается на сортировку в куче. Впрочем, у того факта, что стандарт не диктует реализацию алгоритма, есть и недостаток - можно реализовать очень плохой алгоритм, который соответствует стандарту. Например, реализация scrt() на базе сортировки в куче будет считаться соответствующей стандарту. Конечно, оптимальный алгоритм можно выбрать на основании тестирования, однако нельзя гарантировать, что программный код хронометража будет работать на других платформах.

Помимо перечисленных существуют и другие алгоритмы сортировки элементов. Например, алгоритмы сортировки в куче вызывают функции, непосредственно работающие с кучей (то есть с бинарным деревом, используемым в реализации этих алгоритмов). Алгоритмы сортировки в куче заложены в основу эффективной реализации приоритетньгх очередей (см. с. 438). Вызовы этих алгоритмов, сортирующие все элементы коллекции, выглядят так:

/* сортировка всех элементов * - сложность n+n*log(n) */

niake heap (coll.beginO. coll.endO): sort heap (coll.beginO. coll.endO):

3a дополнительной информацией о кучах и алгоритмах сортировки в куче обращайтесь на с. 396.

Алгоритмы nth element() существуют на тот случай, если вам нужен только Пй упорядоченный элемент или подмножество из п старших или младших зле-