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

std::sortАлгоритм (и его кузены std::partial_sortи std::nth_element) из стандартной библиотеки C ++ в большинстве реализаций сложный и гибридная объединение более элементарных алгоритмов сортировки , таких как выбор сортировки, вставки сортировка, быстрая сортировка, сортировка слиянием, или кучи сортировки.

Здесь и на родственных сайтах, таких как https://codereview.stackexchange.com/, есть много вопросов, связанных с ошибками, сложностью и другими аспектами реализации этих классических алгоритмов сортировки. Большинство предлагаемых реализаций состоят из необработанных циклов, используют манипуляции с индексами и конкретные типы и, как правило, нетривиальны для анализа с точки зрения правильности и эффективности.

Вопрос : как можно реализовать вышеупомянутые классические алгоритмы сортировки с использованием современного C ++?

• нет сырых циклов , но объединяет алгоритмические строительные блоки стандартной библиотеки из<algorithm>
• интерфейс итератора и использование шаблонов вместо манипулирования индексами и конкретных типов
• Стиль C ++ 14 , включая полную Стандартную библиотеку, а также синтаксические шумоподавители, такие как autoпсевдонимы шаблонов, прозрачные компараторы и полиморфные лямбды.

Примечания :

• дальнейшие ссылки на реализации алгоритмов сортировки см. в Википедии , Rosetta Code или http://www.sorting-algorithms.com/
• в соответствии с соглашениями Шона Родителя (слайд 39), необработанный цикл является forциклом длиннее, чем композиция двух функций с оператором. Так f(g(x));или f(x); g(x);или f(x) + g(x);не являются необработанными циклами, и ни один из них не является циклами внутри selection_sortи insertion_sortниже.
• Я следую терминологии Скотта Мейерса, чтобы обозначить текущий C ++ 1y уже как C ++ 14, и обозначить C ++ 98 и C ++ 03 как C ++ 98, так что не расстраивайтесь.
• Как предложено в комментариях @Mehrdad, в конце ответа я приведу четыре реализации в качестве живого примера: C ++ 14, C ++ 11, C ++ 98 и Boost и C ++ 98.
• Сам ответ представлен только на языке C ++ 14. Где уместно, я обозначаю синтаксические и библиотечные различия, где разные языковые версии различаются.

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

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

#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()а также with std::next(), доступны только с C ++ 11 и выше. Для C ++ 98 их нужно написать самому. Есть заменители из Boost.Range в boost::begin()/ boost::end()и Boost.Utility в boost::next().
• std::is_sortedалгоритм доступен только для C ++ 11 и за ее пределами. Для C ++ 98 это может быть реализовано в терминах std::adjacent_findрукописного объекта функции. Boost.Algorithm также предоставляет boost::algorithm::is_sortedв качестве замены.
• 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 нужно написать две перегрузки и использовать подробный 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 имеет только мономорфные лямбды, которые требуют использования вышеуказанного псевдонима шаблона value_type_t.
• В C ++ 98 нужно либо написать отдельный объект функции, либо прибегнуть к подробному std::bind1st/ std::bind2nd/ std::not1типу синтаксиса.
• Boost.Bind улучшает это с помощью синтаксиса boost::bindи _1/ _2placeholder.
• C ++ 11 и более поздние версии также есть std::find_if_not, в то время как C ++ 98 нуждается std::find_ifв std::not1функциональном объекте.

Стиль С ++

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

• Рекомендация Херба Саттера «Почти всегда авто» и рекомендация Скотта Мейерса «Предпочитать авто определенным объявлениям типов» , для которых краткость непревзойденна, хотя ее ясность иногда оспаривается .
• Скотт Мейерс «Различают ()и {}при создании объектов» и последовательно выбирает фигурную инициализацию {}вместо старой доброй инициализации ()в скобках (чтобы обойти все самые неприятные проблемы синтаксического анализа в общем коде).
• Скотт Мейерс "Предпочитать объявления псевдонимов typedefs" . В любом случае для шаблонов это необходимо, и использование его везде вместо typedefэкономии времени и повышения согласованности.
• for (auto it = first; it != last; ++it)В некоторых местах я использую шаблон, чтобы разрешить проверку инварианта цикла для уже отсортированных поддиапазонов. В рабочем коде использование 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), потому что первый элемент гарантированно находится на своем месте и не требует поворота.
• для двунаправленных итераторов бинарный поиск для поиска точки вставки может быть заменен обратным линейным поиском с использованием std::find_if_notалгоритма стандартной библиотеки .

Четыре живых примера ( 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)сложности, сводка должна приводить к сбалансированному разделу входных данных, что в общем случае не может быть гарантировано для O(1)сводки, но может быть гарантировано, если установить стержень в качестве O(N)медианы входного диапазона.

Детали опущены :

• Вышеприведенная реализация особенно уязвима для специальных входных данных, например, она имеет O(N^2)сложность для ввода « органной трубы » 1, 2, 3, ..., N/2, ... 3, 2, 1(потому что середина всегда больше, чем все другие элементы).
• медианный выбор 3 из случайно выбранных элементов из входного диапазона защищает от почти отсортированных входных данных, сложность которых в противном случае ухудшилась быO(N^2).
• Трехстороннее разделение (разделение элементов меньше, равно и больше, чем стержень), как показано двумя вызовами,std::partitionне является самым эффективнымO(N)алгоритмом для достижения этого результата.
• для итераторов с произвольным доступом гарантированная 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, за которой следует O(N)вызов std::partition(который представляет собой однократный прямой переход к кэш-памяти). данные).

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

Если использование O(N)дополнительного пространства не имеет значения, сортировка по слиянию - отличный выбор: это единственный стабильный O(N log 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фаза «сортировки», многократно извлекает максимум и восстанавливает порядок кучи. Стандартная библиотека делает это чрезвычайно простым:

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%).

Еще один маленький и довольно элегантный, изначально найденный в обзоре кода . Я думал, что это стоит поделиться.

Подсчет сортировки

Хотя сортировка подсчета является довольно специализированной, это простой алгоритм целочисленной сортировки, который часто может быть очень быстрым, если значения сортируемых целых чисел не слишком далеко друг от друга. Это, вероятно, идеально, если когда-нибудь понадобится отсортировать коллекцию из миллиона целых чисел, например, между 0 и 100.

Чтобы реализовать очень простую подсчетную сортировку, которая работает как со знаковыми, так и без знака целыми числами, нужно найти самые маленькие и самые большие элементы в коллекции для сортировки; их различие скажет размер массива, который нужно выделить. Затем выполняется второй проход по коллекции для подсчета количества вхождений каждого элемента. Наконец, мы записываем необходимое число каждого целого обратно в исходную коллекцию.

template<typename ForwardIterator>
void counting_sort(ForwardIterator first, ForwardIterator last)
{
    if (first == last || std::next(first) == last) return;

    auto minmax = std::minmax_element(first, last);  // avoid if possible.
    auto min = *minmax.first;
    auto max = *minmax.second;
    if (min == max) return;

    using difference_type = typename std::iterator_traits<ForwardIterator>::difference_type;
    std::vector<difference_type> counts(max - min + 1, 0);

    for (auto it = first ; it != last ; ++it) {
        ++counts[*it - min];
    }

    for (auto count: counts) {
        first = std::fill_n(first, count, min++);
    }
}

Хотя это полезно только в том случае, если известно, что диапазон целых чисел для сортировки мал (обычно не больше, чем размер коллекции для сортировки), если сделать сортировку подсчета более универсальной, это замедлит работу в ее лучших случаях. Если неизвестно, что диапазон мал, можно использовать другой алгоритм, такой как сортировка по основанию , ska_sort или spreadsort .

Детали опущены :

• Мы могли бы пройти границы диапазона значений, принятых алгоритмом в качестве параметров, чтобы полностью избавиться от первого std::minmax_elementпрохода через коллекцию. Это сделает алгоритм еще более быстрым, когда полезный малый предел диапазона известен другими способами. (Это не обязательно должно быть точно; пропускать константу от 0 до 100 все же гораздо лучше, чем дополнительный проход через миллион элементов, чтобы узнать, что истинные границы составляют от 1 до 95. Даже от 0 до 1000 стоило бы того; дополнительные элементы записываются один раз с нуля и читаются один раз).

• Расти countsна лету - это еще один способ избежать отдельного первого прохода. Удвоение countsразмера при каждом увеличении дает амортизированное время O (1) для отсортированного элемента (см. Анализ затрат на вставку хеш-таблицы для доказательства того, что экспоненциальный рост является ключевым). Выращивание в конце для нового maxлегко с std::vector::resizeдобавлением новых обнуленных элементов. Изменение minна лету и вставка новых обнуленных элементов спереди может быть сделано std::copy_backwardпосле увеличения вектора. Затем std::fillобнулить новые элементы.

• Цикл countsприращения является гистограммой. Если данные, скорее всего, будут сильно повторяющимися, а количество бинов невелико, возможно, стоит развернуть несколько массивов, чтобы уменьшить узкое место зависимости данных при сериализации при хранении / перезагрузке в одном и том же бине. Это означает, что большее число обнуляется в начале и больше зацикливается в конце, но оно должно стоить этого на большинстве процессоров для нашего примера миллионов чисел от 0 до 100, особенно если входные данные уже (частично) отсортированы и есть длинные пробеги одного и того же числа.

• В приведенном выше алгоритме мы используем min == maxпроверку для раннего возврата, когда каждый элемент имеет одинаковое значение (в этом случае коллекция сортируется). На самом деле можно вместо этого полностью проверить, отсортирована ли уже коллекция, находя экстремальные значения коллекции без лишних затрат времени (если первый проход все еще является узким местом в памяти с дополнительной работой обновления min и max). Однако такого алгоритма нет в стандартной библиотеке, и написание его было бы более утомительным, чем написание остальной части самой сортировки подсчета. Это оставлено как упражнение для читателя.

• Поскольку алгоритм работает только с целочисленными значениями, можно использовать статические утверждения, чтобы пользователи не допускали очевидных ошибок типов. В некоторых случаях сбой замещения с std::enable_if_tможет быть предпочтительным.

• Хотя современный C ++ классный, будущий C ++ может быть еще круче: структурированные привязки и некоторые части TS Ranges сделают алгоритм еще чище.