Выбор ответа Junior Алгоритмы STL и ranges спрашивают часто обновлено
Стабильность std::sort
Вопрос
Записи отсортированы по имени. Затем их отсортировали std::sort по возрасту. Сохранится ли порядок по имени у людей одного возраста?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Не гарантировано: std::sort нестабилен, есть stablesort. std::sort может переставлять равные элементы как угодно. std::stablesort сохраняет их относительный порядок, на этом построена сортировка «по нескольким колонкам» последовательными стабильными сортировками.
Варианты ответа
- Да: все сортировки STL стабильны, включая
std::sort - Да, если компаратор использует строгое сравнение
< - Нет: порядок равных элементов всегда переворачивается
- Не гарантировано:
std::sortнестабилен, естьstable_sortправильный ответ
Разбор
std::sort может переставлять равные элементы как угодно. std::stable_sort сохраняет их относительный порядок, на этом построена сортировка «по нескольким колонкам» последовательными стабильными сортировками. Другой путь: один std::sort с составным ключом через std::tie.
- Стабилен только
stable_sort(иlist::sort). - Вид компаратора на стабильность не влияет.
- Порядок равных не определён, а не перевёрнут.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.