12.5.2. Алгоритмы сортировки и упорядочения

12.5.2. Алгоритмы сортировки и упорядочения

Четырнадцать алгоритмов сортировки и упорядочения предлагают различные способы упорядочения элементов контейнера. Разбиение (partition) – это разделение элементов контейнера на две группы: удовлетворяющие и не удовлетворяющие некоторому условию. Так, можно разбить контейнер по признаку четности/нечетности чисел или в зависимости от того, начинается слово с заглавной или со строчной буквы. Устойчивый (stable) алгоритм сохраняет относительный порядок элементов с одинаковыми значениями или удовлетворяющих одному и тому же условию. Например, если дана последовательность:

{ "pshew", "honey", "Tigger", "Pooh" }

то устойчивое разбиение по наличию/отсутствию заглавной буквы в начале слова генерирует последовательность, в которой относительный порядок слов в каждой категории сохранен:

{ "Tigger", "Pooh", "pshew", "honey" }

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

inplace_merge(), merge(), nth_element(), partial_sort(),

partial_sort_copy(), partition(), random_shuffle(), reverse(),

reverse_copy(), rotate(), rotate_copy(), sort(), stable_sort(),

stable_partition()