Как реализовать классические алгоритмы сортировки в современном 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

• инструменты итератора, такие как не член std::begin() / std::end() а также с 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 / _2 синтаксис заполнителя.
• C ++ 11 и выше также имеют std::find_if_notтогда как C ++ 98 нужен std::find_if с std::not1 вокруг функционального объекта.

Стиль C ++

Общепринятого стиля C ++ 14 пока нет. Хорошо это или плохо, я внимательно слежу за Скоттом Мейерсом. проект Effective Modern C ++ и Херб Саттерс обновленный 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, С ++ 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),
• 3-х стороннее разделение (разделение элементов меньше, равно и больше, чем стержень), как показано двумя вызовами 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, С ++ 98) тестирование всех пяти алгоритмов на различных входах (не должно быть исчерпывающим или строгим). Просто обратите внимание на огромные различия в LOC: C ++ 11 / C ++ 14 требует около 130 LOC, C ++ 98 и Boost 190 (+ 50%) и C ++ 98 более 270 (+ 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++);
}
}