Ответ
std::sort из заголовка <algorithm> — это гибридный алгоритм сортировки, который в большинстве реализаций (например, в libstdc++ и libc++) представляет собой Introsort.
Как работает Introsort:
- Начинается как быстрая сортировка (Quicksort) с медианой из трёх для выбора опорного элемента.
- Отслеживает глубину рекурсии. Если она превышает
2 * log₂(n), алгоритм переключается на пирамидальную сортировку (Heapsort). Это гарантирует сложность O(n log n) в худшем случае и предотвращает деградацию до O(n²) на специально подобранных данных. - Для маленьких подмассивов (обычно размером менее 16-32 элементов) часто применяется сортировка вставками (Insertion Sort) из-за её эффективности на небольших наборах.
Синтаксис и использование:
#include <algorithm>
#include <vector>
#include <functional>
std::vector<int> data = {5, 1, 4, 2, 8};
// 1. Сортировка по возрастанию (использует operator<)
std::sort(data.begin(), data.end());
// 2. Сортировка по убыванию с использованием функционального объекта
std::sort(data.begin(), data.end(), std::greater<int>());
// 3. Сортировка с пользовательским компаратором (лямбда)
std::sort(data.begin(), data.end(), [](int a, int b) {
return (a % 3) < (b % 3); // Сортировка по остатку от деления на 3
});Ключевые особенности std::sort:
- Требует итераторов произвольного доступа: Работает с
std::vector,std::deque,std::arrayи обычными массивами. Не работает сstd::list(для него есть методlist::sort()). - Нестабильная: Не сохраняет относительный порядок равных элементов. Для стабильной сортировки используйте
std::stable_sort. - Компаратор: Должен обеспечивать строгое слабое упорядочение. Например, для сортировки по убыванию корректно использовать
std::greater<>(), а не[](int a, int b) { return a > b; }(хотя лямбда также допустима).
Ответ 18+ 🔞
А, ну это же классика, ёпта! std::sort — это не просто какая-то там сортировка, это, блядь, целый гибридный зверь под капотом, который в большинстве библиотек зовётся Introsort. И он не дурак, работает с умом.
Как этот хитрожопый Introsort выкручивается:
- Стартует он как быстрая сортировка (Quicksort), да ещё и с умным выбором опорного элемента — медианой из трёх. Не какой-нибудь случайный хуй с горы берёт.
- Но тут главный фокус: он, сука, глубину рекурсии считает. Если чувствует, что закапывается слишком глубоко (больше
2 * log₂(n)), то у него терпения ебать ноль, и он резко переключается на пирамидальную сортировку (Heapsort). Это гениально, потому что худший случай становится O(n log n), и никакие специально подогнанные данные его не взломают. На этом многие наивные реализации быстрой сортировки накрываются медным тазом, а наш — нет. - А для совсем мелких подмассивов (ну там, меньше 16 элементов) он вообще не парится и врубает сортировку вставками (Insertion Sort), потому что на мелочи она — просто ядрёна вошь, быстрее всех.
Как этим пользоваться, чтобы не выглядеть мудем:
#include <algorithm>
#include <vector>
#include <functional>
std::vector<int> data = {5, 1, 4, 2, 8};
// 1. Просто сортировка по возрастанию (использует operator<)
std::sort(data.begin(), data.end()); // Всё, готово.
// 2. Хочешь по убыванию — вот тебе готовый функциональный объект
std::sort(data.begin(), data.end(), std::greater<int>());
// 3. Ну а если надо какую-то свою, ебанутую логику — лямбда в руки
std::sort(data.begin(), data.end(), [](int a, int b) {
return (a % 3) < (b % 3); // Сортировка по остатку от деления на 3, например. Ну а хули?
});Важные фишки, которые надо помнить, чувак:
- Ест только итераторы произвольного доступа: То есть
std::vector,std::deque,std::arrayи голые массивы — пожалуйста. А вотstd::listсюда не суй — у него свой методlist::sort()есть, распиздяй. - Нестабильный, блядь: Равные элементы могут перепутаться. Если для тебя это как вилкой в глаз, бери
std::stable_sort. - С компаратором не обосрись: Он должен строгое слабое упорядочение обеспечивать. Для сортировки по убыванию проще и правильнее
std::greater<>()взять, хотя и лямбда[](int a, int b) { return a > b; }сработает. Но ты чувствуешь подвох? Вот и я чувствую. Лучше не выёживайся без нужды.