К содержанию
Quantoros

Когда выбирать 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

Похожие вопросы