Все началось с того, что я почему-то написал свою реализацию классического алгоритма быстрой сортировки QuickSort. И все бы хорошо, но я, конечно, решил померяться достоинством с STL’ой реализацией. Результат был очевиден, и я даже не хочу приводить цифры.
В общем, я открыл файл algorithm
из STL’я в Visual Studio 2008 и часок покопался в нем. Вот результаты моих “исследований”.
Начнем с нестабильной сортировки std::sort().
QuickSort
(почти как у меня)if
‘ами)S = 1/8*N
) и для троиц элементов (1, S, 2*S)
, (N/2 - S, N/2, N/2 + S)
и (N - 2*S, N - S, N)
делается такая же минисортировка, как и на предыдущем шаге (где число элементов было меньше 40)QuickSort
процедура деления фрагмента на две части с использованием опорного элемента (цикл по перебрасыванию элементов, меньших опорного направо, а больших — налево)Количество рекурсивных операций не идет до победного конца, как в чистом QuickSort
. Если количество итераций (процедур разделения массива) превысило 1.5*log2(N)
, где N длина всего массива, то рекурсивные операции прекращаются. Если количество оставшихся недосортированных элементов меньше 32-х, то фрагмент досортируется методом вставки InsertionSort
(этот метод имеет общую сложность O(N2)
и для больших массивов не используется, но на малых длинах он быстрее всех из-за простоты). Если же остается более 32-х элементов, то досортировка происходит пирамидальным методом HeapSort
в чистом его виде.
Видимо все эти ухищрения для уменьшения накладных расходов QuickSort
на малых массивах.
Вот такая вот далеко непрямолинейная реализация.
Далее.
Стабильная сортировка std::stable_sort() реализована алгоримом слияния MergeSort
. Особых ухищрений по сравнению с чистным алгоритмом я не нашел. Разве что малые фрагменты (короче 32-х элементов) досортировываются методом вставки InsertionSort, как и в случае с QuickSort.
Частичая сортировка std::partial_sort() реализована в чистом виде пирамидальным методом HeapSort.
Вывод: Читать исходники очень интересно. Особенно хорошие исходники.