Какие алгоритмы используют популярные компиляторы C ++ для std :: sort и std :: stable_sort?

Какие алгоритмы используют популярные компиляторы C ++ для std :: sort и std :: stable_sort? Я знаю, что стандарт дает только определенные требования к производительности, но я хотел бы знать, какие алгоритмы популярные реализации используют на практике.

Ответ был бы более полезным, если бы он приводил ссылки для каждой реализации.

16

Решение

Прежде всего: компиляторы не предоставляют любой реализация std::sort, Хотя традиционно каждый компилятор поставляется в комплекте с реализацией стандартной библиотеки (которая в значительной степени зависит от встроенных компиляторов), теоретически вы можете поменять одну реализацию на другую. Один очень хороший пример — Clang компилирует как libstdc ++ (традиционно упакованный с gcc), так и libc ++ (совершенно новый).

Теперь, когда это вне пути …

std::sort традиционно был реализован как интро сортировки. С точки зрения высокого уровня это означает относительно стандартную реализацию быстрой сортировки (с некоторым медианным зондированием, чтобы избежать O (n2) наихудший случай) в сочетании с процедурой сортировки для небольших входных данных. Реализация libc ++, однако, немного отличается и ближе к TimSort: она обнаруживает уже отсортированные последовательности во входных данных и избегает их повторной сортировки, что приводит к поведению O (n) на полностью отсортированном вводе. Он также использует оптимизированные сети сортировки для небольших входов.

std::stable_sort с другой стороны, это более сложный характер. Это можно экстраполировать из самой формулировки Стандарта: сложность O (n log n) если может быть выделено достаточно дополнительной памяти (намекает на Сортировка слиянием), но вырождается в O (n log2 н) если нет.

18

Другие решения

Если мы возьмем в качестве примера gcc, то увидим, что он std::sort и слияние для std::stable_sort.

Если вы пройдете через код libc ++ вы увидите, что он также использует mergesort для std::stable_sort если диапазон достаточно большой.

Также следует отметить, что, хотя общий подход всегда является одним из вышеупомянутых, они все высоко оптимизированы для различных особых случаев.

6

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector