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

Question

Как реализовать классические алгоритмы сортировки в современном 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. Там, где это уместно, я обозначаю синтаксические и библиотечные различия, когда разные языковые версии различаются.

346

c++ algorithm sorting c++14 c++-faq

Источник

user819272 09 июл '14 в 09:59

3 ответа

Решение

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

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

Хотя сортировка подсчета является довольно специализированной, это простой алгоритм целочисленной сортировки, который часто может быть очень быстрым, если значения сортируемых целых чисел не слишком далеко друг от друга. Это, вероятно, идеально, если когда-нибудь понадобится отсортировать коллекцию из одного миллиона целых чисел, например, от 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++ может быть еще круче: структурированные привязки и некоторые части Ranges TS сделают алгоритм еще чище.

16

Источник

user1364752 08 май '16 в 22:55

Версии Visual Studio до 2015 года использовали сортировку слиянием снизу вверх для связанного списка, но переключились на менее эффективную (из-за сканирования списков для разделения их с помощью std::next) сортировку слиянием сверху вниз для связанного списка, когда она была изменена, чтобы не обрабатывать распределитель по умолчанию с использованием алгоритма на основе итератора, который также обеспечивал безопасность исключений, если сравнение (определяемое пользователем) вызывало исключение (в более старой версии исключение сравнения теряло часть списка во внутреннем массиве). Когда это впервые было поставлено под сомнение, я предположил, что есть некоторые проблемы с реализацией сортировки слиянием снизу вверх на основе итератора для связанного списка, но позже решил, что проблем нет. Единственная «умная» часть моей реализации — использование std::list::end() (константа) для указания пустого подсписка (поскольку итератор не может быть нулевым).

/questions/4162539/stdlistsort-pochemu-vnezapnyij-perehod-na-nishodyaschuyu-strategiyu/4162540#4162540

0

Источник

user3282056 15 сен '22 в 00:09

Другие вопросы по тегам c++ algorithm sorting c++14 c++-faq

user819272 09 июл '14 в 09:59 2014-07-09 09:59 · Accepted Answer · 2014-07-09 09:59

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

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

#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++14 пока нет. Хорошо это или плохо, но я внимательно слежу за проектом Скотта Мейерса " Эффективный современный С ++" и обновленным GotW Херба Саттера. Я использую следующие рекомендации по стилю:

Рекомендация Херба Саттера "Почти всегда авто" и рекомендация Скотта Мейерса "Предпочитать авто определенным объявлениям типов", для которых краткость непревзойденна, хотя ее ясность иногда оспаривается.
Скотта Мейерса "Отличить" () а также {} при создании объектов "и последовательно выбирайте braced-initialization {} вместо старой доброй инициализации в скобках () (чтобы обойти все самые неприятные проблемы в общем коде).
Скотт Мейерс "Предпочитают объявления псевдонимов 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%).