Mediumалгоритмы
Чем std::partition отличается от std::sort?
1Постановка
Разберём, что от вас хотят в этом вопросе и как к нему подступиться на собеседовании.
2Решение
std::partition переставляет элементы так, что удовлетворяющие pred идут раньше остальных, без упорядочения внутри групп. O(n), быстрее sort (O(n log n)).
std::vector<int> v{1, 2, 3, 4, 5, 6};
// Чётные вперёд, нечётные назад — без сортировки
auto it = std::partition(v.begin(), v.end(),
[](int x){ return x % 2 == 0; });
// [begin, it) — чётные, [it, end) — нечётные
std::stable_partition(v.begin(), v.end(), pred); // сохраняет порядок- sort — полное упорядочение; partition — только разнести по группам;
std::partition_point— бинарный поиск точки раздела в partitioned диапазоне;- Для top-K без полной сортировки —
std::partial_sortилиstd::nth_element.
3Как отвечать
- Сначала уточните условия и ограничения, покажите аналитическое мышление.
- Рассуждайте вслух — интервьюеру важен ход мысли, а не только финальный ответ.
- Оцените сложность по времени и памяти (Big-O), если это алгоритмический вопрос.
💡
На реальном собеседовании Alffert подскажет развёрнутый ответ в реальном времени.