Когда выбирать sort, stablesort, partialsort и nthelement?
C++Уровень: ПрактикаSTL Containers & Iterators
Когда выбирать sort, stable_sort, partial_sort и nth_element?
Подсказки
- Уточните типы, время жизни объектов и то, что определяется на этапе компиляции.
- Проверьте гарантии стандарта отдельно от поведения конкретного компилятора.
Ответ
sort полностью сортирует диапазон за O(n log n) сравнений, не сохраняя порядок эквивалентных элементов; ему нужны итераторы произвольного доступа. stable_sort сохраняет этот порядок; при достаточной вспомогательной памяти оценка O(n log n), иначе возможна O(n log² n). partial_sort упорядочивает только первые k наименьших элементов, обычно O(n log k). nth_element ставит на позицию нужную порядковую статистику и разделяет остальные элементы по отношению к ней, но не сортирует части; средняя оценка линейна. Он удобен для медианы и квантилей.
Примеры из источника:
#include <algorithm>
#include <vector>
int main() {
std::vector v{3, 1, 4, 1, 5, 9, 2, 6};
std::sort(v.begin(), v.end()); // ascending
std::sort(v.begin(), v.end(), std::greater<>{}); // descending
// custom comparator
std::sort(v.begin(), v.end(), [](int a, int b) { return a > b; });
}
#include <algorithm>
#include <vector>
struct Item {
int priority;
int order;
};
int main() {
std::vector<Item> items{{1, 1}, {2, 2}, {1, 3}, {2, 4}};
// stable_sort preserves original order for equal elements
std::stable_sort(items.begin(), items.end(),
[](auto &a, auto &b) { return a.priority < b.priority; });
// items with same priority keep their original relative order
}
#include <algorithm>
#include <vector>
int main() {
std::vector v{5, 7, 4, 2, 8, 6, 1, 9, 0, 3};
// sort only first 3 elements
std::partial_sort(v.begin(), v.begin() + 3, v.end());
// v: {0, 1, 2, ...} first 3 are sorted, rest unspecified
}
#include <algorithm>
#include <vector>
int main() {
std::vector v{5, 6, 4, 3, 2, 6, 7, 9, 3};
// find median (middle element)
auto mid = v.begin() + v.size() / 2;
std::nth_element(v.begin(), mid, v.end());
// *mid is now the median value
}
Материалы источника:
Источник и лицензия: C/C++ Interview Cheatsheet — Chang Ning Tsai · MIT · перевод: Quantoros