На этом шаге мы закончим сравнение алгоритмов сортировки.
Помимо перечисленных на предыдущем шаге существуют и другие алгоритмы сортировки элементов. Например, алгоритмы сортировки в куче вызывают функции, непосредственно работающие с кучей (то есть с бинарным деревом, используемым в реализации этих алгоритмов). Алгоритмы сортировки в куче заложены в основу эффективной реализации приоритетных очередей. Вызовы этих алгоритмов, сортирующие все элементы коллекции, выглядят так:
// Сортировка всех элементов // - сложность n+n*log(n) make_heap (coll.begin(), coll.end()); sort_heap (coll.begin(), coll.end());
Алгоритмы nth_element() существуют на тот случай, если вам нужен только n-й упорядоченный элемент или подмножество из n старших или младших элементов (неупорядоченное). Алгоритм nth_element() разделяет элементы на два подмножества в соответствии с критерием сортировки. Впрочем, задача также может быть решена алгоритмами partition() и stable_partition(). Различия между этими алгоритмами заключаются в следующем.
- Алгоритму nth_element() передается требуемое количество элементов в первой части (а следовательно, и
во второй). Пример:
// Перемещение четырех наименьших элементов в начало nth_element (coll.begin(), // Начало интервала coll.begin()+3, // Позиция, отделяющая первую часть от второй coll.end()); // Конец интервала
Но после вызова невозможно сказать, по какому критерию первая часть отличается от второй. Более того, в обеих частях могут присутствовать элементы, совпадающие по значению с n-м элементом.
- Алгоритму partition() передается конкретный критерий сортировки, определяющий различия между
первой и второй частями:
// Перемещение всех элементов, меньших 7, в начало vector<int>::iterator pos; pos = partition (coll.begin(), coll.end(), // Интервал bind2nd(less<int>(),7)); // Критерий
На этот раз после вызова невозможно сказать, сколько элементов входит в первую и вторую части. Возвращаемый итератор pos указывает на первый элемент второй части, которая содержит все элементы, не соответствующие критерию.
- Алгоритм stable_partition() в целом аналогичен partition(), но он дополнительно гарантирует сохранение порядка следования элементов в обеих частях по отношению к другим элементам, входящим в ту же часть.
Любому алгоритму сортировки в необязательном аргументе всегда можно передавать критерий сортировки. По умолчанию критерием сортировки является объект функции less<>, а элементы сортируются по возрастанию значений.
Как и в случае с модифицирующими алгоритмами, приемником алгоритмов сортировки не может быть ассоциативный контейнер, поскольку элементы ассоциативного контейнера считаются константными.
Кроме того, алгоритмы сортировки не могут вызываться для списков, поскольку списки не поддерживают итераторы произвольного доступа. Впрочем, для сортировки элементов в списках определена функция sort() (смотри 204 шаг).
На следующем шаге мы рассмотрим алгоритмы упорядоченных интервалов.
