Как реализовать классические алгоритмы сортировки в современном C++?

алгоритмические строительные блоки

начнем с сборки алгоритмических строительных блоков из стандартной библиотеки:

#include <algorithm>    // min_element, iter_swap, 
                        // upper_bound, rotate, 
                        // partition, 
                        // inplace_merge,
                        // make_heap, sort_heap, push_heap, pop_heap,
                        // is_heap, is_sorted
#include <cassert>      // assert 
#include <functional>   // less
#include <iterator>     // distance, begin, end, next

• инструменты итератора, такие как non-member std::begin()/std::end() а также с std::next() доступны только с C++11 и выше. Для C++98 это нужно написать самому. Есть заменители от Boost.Диапазон в boost::begin()/boost::end(), и от наддува.Утилита в boost::next().
• the std::is_sorted алгоритм доступен только для C++11 и выше. Для C++98 это может быть реализовано в терминах std::adjacent_find и рукописный объект функции. Повышение.Алгоритм также обеспечивает boost::algorithm::is_sorted в качестве замены.
• the std::is_heap алгоритм доступен только для C++11 и выше.

синтаксические вкусности

в C++14 обеспечивает прозрачный компараторы формы std::less<> которые действуют полиморфно на их аргументы. Это позволяет избежать необходимости предоставлять тип итератора. Это может быть использовано в сочетании с C++11 это аргументы шаблона функции по умолчанию создать одна перегрузка для сортировки алгоритмов, которые принимают < в сравнении и те, которые имеют определенный пользователем объект функции сравнения.

template<class It, class Compare = std::less<>>
void xxx_sort(It first, It last, Compare cmp = Compare{});

в C++11, можно определить многоразовые псевдоним шаблона для извлечения итератора тип значения, который добавляет незначительный беспорядок к сигнатурам алгоритмов сортировки:

template<class It>
using value_type_t = typename std::iterator_traits<It>::value_type;

template<class It, class Compare = std::less<value_type_t<It>>>
void xxx_sort(It first, It last, Compare cmp = Compare{});

в C++98 нужно написать две перегрузки и использовать verbose typename xxx<yyy>::type синтаксис

template<class It, class Compare>
void xxx_sort(It first, It last, Compare cmp); // general implementation

template<class It>
void xxx_sort(It first, It last)
{
    xxx_sort(first, last, std::less<typename std::iterator_traits<It>::value_type>());
}

• еще одна синтаксическая тонкость заключается в том, что C++14 облегчает перенос пользовательских компараторов через полиморфные лямбды (с auto параметры, которые выводятся как аргументы шаблона функции).
• C++11 имеет только мономорфный лямбды, которые требуют использования вышеуказанного шаблона alias value_type_t.
• в C++98 нужно либо написать автономный объект функции, либо прибегнуть к подробному std::bind1st/std::bind2nd/std::not1 тип синтаксиса.
• импульс.Bind улучшает это с помощью boost::bind и _1/_2 синтаксис заполнителя.
• C++11 и за его пределами тоже есть std::find_if_not, в то время как C++98 нуждается std::find_if С std::not1 вокруг функция объект.

Стиль C++

пока нет общепринятого стиля C++14. К лучшему или к худшему, я внимательно слежу за Скоттом Мейерсом проект эффективного современного C++ и Херба Саттера обновленный GotW. Я использую следующие рекомендации по стилю:

• Херб Саттер "Почти Всегда "Авто"" и Скотта Мейерса "предпочитаю авто объявления определенного типа" рекомендация, для которой краткость непревзойденна, хотя ее ясность иногда спорная.
• Скотт Мейерс "выделить () и {} при создании объектов" и последовательно выберите braced-initialization {} вместо старой доброй инициализации в скобках () (для того, чтобы шаг в сторону все наиболее досадные проблемы разбора в общем коде).
• Скотт Мейерс "предпочитают заявлений псевдоним для определения типов". Для шаблонов это необходимо в любом случае, и использовать его везде вместо typedef экономит время и добавляет последовательности.
• я использую for (auto it = first; it != last; ++it) pattern в некоторых местах, чтобы обеспечить инвариантную проверку цикла для уже отсортированных поддиапазонов. В производственном коде, использование while (first != last) и ++first где-то внутри цикл может быть немного лучше.

сортировка выбор

сортировка выбор никак не адаптируется к данным, поэтому его время выполнения всегда O(N²). Однако сортировка выбора имеет свойство минимизация количества свопов. В приложениях, где стоимость замены элементов высока, выбор сортировки очень хорошо может быть алгоритм выбора.

реализовать его с помощью стандарта Библиотека, многократно использовать std::min_element чтобы найти оставшийся минимальный элемент, и iter_swap, чтобы поменять его на место:

template<class FwdIt, class Compare = std::less<>>
void selection_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})
{
    for (auto it = first; it != last; ++it) {
        auto const selection = std::min_element(it, last, cmp);
        std::iter_swap(selection, it); 
        assert(std::is_sorted(first, std::next(it), cmp));
    }
}

обратите внимание, что selection_sort имеет уже обработанный диапазон [first, it) сортируется как его инвариант цикла. Минимальные требования вперед итераторы против std::sortитераторы произвольного доступа.

подробности опущу:

• сортировка выбора может быть оптимизирована с помощью раннего теста if (std::distance(first, last) <= 1) return; (или для прямых / двунаправленных итераторов:if (first == last || std::next(first) == last) return;).
• на двунаправленные итераторы, вышеуказанный тест можно совместить с петлей над интервалом [first, std::prev(last)), потому что последний элемент гарантированно является минимальным оставшимся элементом и не требует замены.

сортировка вставками

хотя это один из элементарных алгоритмов сортировки с O(N²) в худшем случае времени, вставки сортировка это алгоритм выбора либо когда данные почти отсортированы (потому что это адаптивные) или когда размер проблемы мал (потому что он имеет низкие накладные расходы). По этим причинам, и потому что это тоже стабильный, сортировка вставки часто используется в качестве рекурсивного базового случая (когда размер проблемы мал) для более высоких алгоритмов сортировки разделения и завоевания, таких как сортировка слиянием или быстрая сортировка.

для реализации insertion_sort со стандартной библиотекой, повторно использовать std::upper_bound, чтобы найти место, где текущий элемент должен идти, и использовать std::rotate чтобы переместить остальные элементы вверх в диапазоне ввода:

template<class FwdIt, class Compare = std::less<>>
void insertion_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})
{
    for (auto it = first; it != last; ++it) {
        auto const insertion = std::upper_bound(first, it, *it, cmp);
        std::rotate(insertion, it, std::next(it)); 
        assert(std::is_sorted(first, std::next(it), cmp));
    }
}

обратите внимание, что insertion_sort имеет уже обработанный диапазон [first, it) сортируется как его инвариант цикла. Сортировка вставки также работает с прямыми итераторами.

подробности опущу:

• сортировка вставки может быть оптимизирована с ранним тест if (std::distance(first, last) <= 1) return; (или для прямых / двунаправленных итераторов:if (first == last || std::next(first) == last) return;) и цикл по интервалу [std::next(first), last), потому что первый элемент гарантированно будет на месте и не требует поворота.
• на двунаправленные итераторы, двоичный поиск для поиска точки вставки может быть заменен на обратный линейный поиск использование стандартной библиотеки .

четыре Живые Примеры (C++14,C++11,C++98 и Boost,C++98) для фрагмента ниже:

using RevIt = std::reverse_iterator<BiDirIt>;
auto const insertion = std::find_if_not(RevIt(it), RevIt(first), 
    [=](auto const& elem){ return cmp(*it, elem); }
).base();

• для случайных входов это дает O(N²) сравнения, но это улучшает до O(N) сравнения для почти отсортированных входов. Двоичный поиск всегда использует O(N log N) сравнения.
• для малых входных диапазонов, тем лучше локальность памяти (кэш, предварительная выборка) линейного поиска также может доминировать в двоичном поиске (это, конечно, следует проверить).

быстрая сортировка

при аккуратном выполнении, быстрая сортировка является надежным и имеет O(N log N) ожидаемая сложность, но с O(N²) наихудшая сложность, которая может быть вызвана с помощью противно выбранных входных данных. Когда стабильная сортировка не требуется, быстрая сортировка является отличным универсальным средством род.

даже для самых простых версий, быстрая сортировка довольно немного сложнее реализовать с помощью стандартной библиотеки, чем другие классические алгоритмы сортировки. Подход ниже использует несколько утилит итератора, чтобы найти средний элемент входной диапазон [first, last) в качестве опоры, а затем использовать два вызова std::partition (которые O(N)) для трехстороннего разбиения входного диапазона на сегменты элементов, которые меньше, равны и больше, чем выбранная ось поворота, соответственно. Наконец, рекурсивно сортируются два внешних сегмента с элементами меньше и больше оси вращения:

template<class FwdIt, class Compare = std::less<>>
void quick_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})
{
    auto const N = std::distance(first, last);
    if (N <= 1) return;
    auto const pivot = *std::next(first, N / 2);
    auto const middle1 = std::partition(first, last, [=](auto const& elem){ 
        return cmp(elem, pivot); 
    });
    auto const middle2 = std::partition(middle1, last, [=](auto const& elem){ 
        return !cmp(pivot, elem);
    });
    quick_sort(first, middle1, cmp); // assert(std::is_sorted(first, middle1, cmp));
    quick_sort(middle2, last, cmp);  // assert(std::is_sorted(middle2, last, cmp));
}

тем не менее, быстрая сортировка довольно сложно получить правильный и эффективный, так как каждый из вышеперечисленных шагов должен быть тщательно проверен и оптимизирован для кода уровня производства. В частности, для O(N log N) сложность, pivot должен привести к сбалансированному разделу входных данных, который не может быть гарантирован в целом для O(1) pivot, но который может быть гарантирован, если установить pivot как O(N) медиана входного диапазона.

подробности опущу:

• вышеуказанная реализация особенно уязвима для специальных входов, например, она имеет O(N^2) сложность для "орган" ввод 1, 2, 3, ..., N/2, ... 3, 2, 1 (потому что середина-это всегда больше, чем все остальные элементы).
• медиана-3 pivot выбор из случайно выбранных элементов от входного диапазона защищает от почти отсортированных входов, для которых сложность в противном случае ухудшилась бы до O(N^2).
• 3-полосная разметка (разделительные элементы меньше, равны и больше, чем pivot), как показано на двух вызовах std::partition не самый эффективный для достижения этого результата.
• для итераторы произвольного доступа гарантия O(N log N) сложность может быть достигнута через медианный выбор оси используя std::nth_element(first, middle, last), а затем рекурсивные вызовы quick_sort(first, middle, cmp) и quick_sort(middle, last, cmp).
• эта гарантия приходит на цену, однако, потому что постоянн фактор O(N) сложность std::nth_element может быть дороже, чем O(1) сложность медианы-3 pivot с последующим O(N) вызов std::partition (который является кэш-дружественный одиночный прямой проход над данными).

сортировка слиянием

при использовании O(N) дополнительное пространство не имеет никакого значения, тогда сортировка слиянием является отличным выбором: он является единственным стабильный сортировка.

это просто реализовать с помощью стандартных алгоритмов: используйте несколько утилит итератора, чтобы найти середину входного диапазона [first, last) и объединить два рекурсивно сортировка сегментов с помощью std::inplace_merge:

template<class BiDirIt, class Compare = std::less<>>
void merge_sort(BiDirIt first, BiDirIt last, Compare cmp = Compare{})
{
    auto const N = std::distance(first, last);
    if (N <= 1) return;                   
    auto const middle = std::next(first, N / 2);
    merge_sort(first, middle, cmp); // assert(std::is_sorted(first, middle, cmp));
    merge_sort(middle, last, cmp);  // assert(std::is_sorted(middle, last, cmp));
    std::inplace_merge(first, middle, last, cmp); // assert(std::is_sorted(first, last, cmp));
}

сортировка слиянием требует двунаправленных итераторов, узким местом является std::inplace_merge. Обратите внимание, что при сортировке связанных списков для сортировки слиянием требуется только O(log N) дополнительное пространство (для рекурсии). Последний алгоритм реализуется с помощью std::list<T>::sort в стандартной библиотеке.

куча вроде

куча вроде прост в реализации, выполняет O(N log N) сортировка на месте, но не является стабильный.

первый круг O(N) фаза "heapify", помещает массив в порядок кучи. Второй цикл,O(N log N) фаза "sortdown", многократно извлекает максимум и восстанавливает порядок кучи. Стандартная библиотека делает это чрезвычайно простым:

template<class RandomIt, class Compare = std::less<>>
void heap_sort(RandomIt first, RandomIt last, Compare cmp = Compare{})
{
    lib::make_heap(first, last, cmp); // assert(std::is_heap(first, last, cmp));
    lib::sort_heap(first, last, cmp); // assert(std::is_sorted(first, last, cmp));
}

в случае, если вы считаете это "обман", чтобы использовать std::make_heap и std::sort_heap, вы можете пойти на один уровень глубже и написать эти функции самостоятельно в терминах std::push_heap и std::pop_heap, соответственно:

namespace lib {

// NOTE: is O(N log N), not O(N) as std::make_heap
template<class RandomIt, class Compare = std::less<>>
void make_heap(RandomIt first, RandomIt last, Compare cmp = Compare{})
{
    for (auto it = first; it != last;) {
        std::push_heap(first, ++it, cmp); 
        assert(std::is_heap(first, it, cmp));           
    }
}

template<class RandomIt, class Compare = std::less<>>
void sort_heap(RandomIt first, RandomIt last, Compare cmp = Compare{})
{
    for (auto it = last; it != first;) {
        std::pop_heap(first, it--, cmp);
        assert(std::is_heap(first, it, cmp));           
    } 
}

}   // namespace lib

стандартная библиотека определяет как push_heap и pop_heap как сложность O(log N). Обратите внимание, однако, что внешний цикл по диапазону [first, last) результаты O(N log N) сложности make_heap, а std::make_heap только O(N) сложности. Для общего O(N log N) сложность heap_sort это не важно.

подробности опущу:O(N) реализация make_heap

тестирование

здесь четыре Живые Примеры (C++14,C++11,C++98 и Boost,C++98) тестирование всех пяти алгоритмов на различных входах (не должно быть исчерпывающим или строгим). Просто обратите внимание на огромные различия в LOC: C++11 / C++14 нужно около 130 LOC, C++98 и Boost 190 (+50%) и C++98 более 270 (+100%).