Mediumалгоритмы
Чем std::sort стабилен?
1Постановка
Разберём, что от вас хотят в этом вопросе и как к нему подступиться на собеседовании.
2Решение
std::sort — НЕ стабилен: равные элементы могут поменять порядок. Для стабильной сортировки — std::stable_sort, сохраняющий относительный порядок равных.
std::vector<int> v{3, 1, 2};
std::sort(v.begin(), v.end()); // НЕ стабилен, обычно быстрее (introsort)
std::stable_sort(v.begin(), v.end()); // стабилен, нужен доп. буфер
// Связанные алгоритмы
std::partial_sort(v.begin(), v.begin()+3, v.end()); // первые K элементов
std::nth_element(v.begin(), v.begin()+2, v.end()); // элемент на нужной позиции- Разница важна, когда у объектов есть «вторичные» характеристики, не учтённые в компараторе;
stable_sortобычно O(n log n) с большим overhead по памяти и времени;- Для C++20
ranges::sortпринимает контейнер напрямую.
3Как отвечать
- Сначала уточните условия и ограничения, покажите аналитическое мышление.
- Рассуждайте вслух — интервьюеру важен ход мысли, а не только финальный ответ.
- Оцените сложность по времени и памяти (Big-O), если это алгоритмический вопрос.
💡
На реальном собеседовании Alffert подскажет развёрнутый ответ в реальном времени.