Jak zaimplementować klasyczne algorytmy sortowania we współczesnym C ++?

std::sortAlgorytm (i jego kuzyni std::partial_sorti std::nth_element) z C ++ Standard Library w większości implementacji skomplikowanej i hybrydowe połączenie więcej podstawowych algorytmów sortowania , takich jak wybór rodzaju, insercji sortowania szybkiego sortowania, łączenia sortowania lub sortowania sterty.

Tutaj i na siostrzanych stronach, takich jak https://codereview.stackexchange.com/, jest wiele pytań związanych z błędami, złożonością i innymi aspektami implementacji tych klasycznych algorytmów sortowania. Większość oferowanych implementacji składa się z surowych pętli, wykorzystuje manipulację indeksem i konkretne typy i generalnie nie jest trywialna do analizy pod kątem poprawności i wydajności.

Pytanie : jak można zaimplementować wyżej wymienione klasyczne algorytmy sortowania przy użyciu nowoczesnego C ++?

• brak surowych pętli , ale połączenie algorytmicznych elementów składowych biblioteki standardowej z<algorithm>
• interfejs iteratora i użycie szablonów zamiast manipulowania indeksem i konkretnych typów
• Styl C ++ 14 , w tym pełna Biblioteka Standardowa, a także składniowe tłumiki szumów, takie jak autoaliasy szablonów, przezroczyste komparatory i polimorficzne lambdy.

Uwagi :

• dalsze odniesienia na temat implementacji algorytmów sortowania można znaleźć w Wikipedii , Kodzie Rosetta lub http://www.sorting-algorithms.com/
• zgodnie z konwencjami Seana Parenta (slajd 39), surowa pętla ma pętlę fordłuższą niż połączenie dwóch funkcji z operatorem. Więc f(g(x));albo f(x); g(x);czy f(x) + g(x);nie są surowe pętle, a nie są pętle selection_sorti insertion_sortponiżej.
• Postępuję zgodnie z terminologią Scotta Meyersa, aby oznaczyć obecny C ++ 1y już jako C ++ 14 oraz C ++ 98 i C ++ 03 zarówno jako C ++ 98, więc nie rozpalaj mnie za to.
• Jak zasugerowano w komentarzach @Mehrdad, podam na końcu odpowiedzi cztery implementacje: C ++ 14, C ++ 11, C ++ 98 oraz Boost i C ++ 98.
• Sama odpowiedź została przedstawiona wyłącznie w kategoriach C ++ 14. W stosownych przypadkach wskazuję różnice składniowe i biblioteczne w przypadku różnych wersji językowych.

Algorytmiczne elementy składowe

Zaczynamy od złożenia algorytmicznych bloków konstrukcyjnych z biblioteki standardowej:

#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

• narzędzia iteratora, takie jak non-member std::begin()/ std::end()oraz as std::next()są dostępne tylko od wersji C ++ 11 i późniejszych. W przypadku C ++ 98 należy je napisać samodzielnie. Istnieją substytuty z Boost.Range w boost::begin()/ boost::end()i od Boost.Utility w boost::next().
• std::is_sortedalgorytm jest dostępna tylko dla c ++ 11 i poza nią. W przypadku C ++ 98 można to zaimplementować w postaci std::adjacent_findobiektu funkcji napisanego ręcznie. Boost.Algorytm zapewnia również boost::algorithm::is_sortedjako substytut.
• std::is_heapalgorytm jest dostępna tylko dla c ++ 11 i poza nią.

Składniowe gadżety

C ++ 14 zapewnia przejrzyste komparatory formy, std::less<>które działają polimorficznie na ich argumenty. Pozwala to uniknąć konieczności podawania typu iteratora. Można tego użyć w połączeniu z domyślnymi argumentami szablonu funkcji w C ++ 11, aby utworzyć pojedyncze przeciążenie dla algorytmów sortujących, które biorą <za porównanie, oraz tych, które mają zdefiniowany przez użytkownika obiekt funkcji porównania.

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

W C ++ 11 można zdefiniować alias szablonu wielokrotnego użytku, aby wyodrębnić typ wartości iteratora, co dodaje drobne zakłócenia do podpisów algorytmów sortowania:

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{});

W C ++ 98 trzeba napisać dwa przeciążenia i użyć pełnej typename xxx<yyy>::typeskładni

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>());
}

• Kolejną zaletą syntaktyczną jest to, że C ++ 14 ułatwia pakowanie komparatorów zdefiniowanych przez użytkownika za pomocą polimorficznych lambd (z autoparametrami, które są wywnioskowane jak argumenty szablonu funkcji).
• C ++ 11 ma tylko jednomorficzne lambdy, które wymagają użycia powyższego aliasu szablonu value_type_t.
• W C ++ 98 należy napisać autonomiczny obiekt funkcji lub zastosować pełną składnię std::bind1st/ std::bind2nd/ std::not1.
• Boost.Bind poprawia to dzięki składni boost::bindi _1/ _2placeholder.
• C ++ 11 i poza nim również std::find_if_not, podczas gdy C ++ 98 potrzeby std::find_ifz std::not1całego obiektu funkcyjnego.

Styl C ++

Nie ma jeszcze ogólnie akceptowanego stylu C ++ 14. Na dobre lub na złe, uważnie śledzę projekt Scotta Meyersa Effective Modern C ++ i odnowiony GotW . Korzystam z następujących zaleceń dotyczących stylu:

• Zalecenia Herb Suttera „Prawie zawsze auto” i zalecenie Scotta Meyersa „Wolę auto od deklaracji określonego typu” , dla których zwięzłość nie ma sobie równych, chociaż jego jasność jest czasem kwestionowana .
• Scott Meyers „Rozróżnij ()i {}podczas tworzenia obiektów” i konsekwentnie wybieraj opcję inicjacji usztywnionej {}zamiast starej dobrej inicjalizacji ()w nawiasach (aby pominąć wszystkie najbardziej irytujące kwestie w kodzie ogólnym).
• Scott Meyers „Wolę deklaracje aliasów niż typedefs” . W przypadku szablonów jest to i tak konieczne, a używanie go wszędzie zamiast typedefoszczędzać czas i zapewnia spójność.
• for (auto it = first; it != last; ++it)W niektórych miejscach używam wzorca, aby umożliwić niezmienne sprawdzanie pętli dla już posortowanych podzakresów. W kodzie produkcyjnym użycie while (first != last)i ++firstgdzieś wewnątrz pętli może być nieco lepsze.

Sortuj wybór

Sortowanie selekcji w żaden sposób nie dostosowuje się do danych, więc jego czas działania jest zawszeO(N²). Jednak sortowanie według wyboru ma właściwość minimalizowania liczby zamian . W aplikacjach, w których koszt wymiany elementów jest wysoki, algorytm wyboru może być bardzo dobrze sortowany.

Aby zaimplementować go przy użyciu biblioteki standardowej, kilkakrotnie użyj, std::min_elementaby znaleźć pozostały minimalny element i iter_swapzamienić go na miejsce:

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));
    }
}

Zauważ, że selection_sortjuż przetworzony zakres został [first, it)posortowany jako niezmiennik pętli. Minimalne wymagania to iteratory przesyłania dalej , w porównaniu do std::sortiteratorów dostępu swobodnego.

Szczegóły pominięte :

• sortowanie wyboru można zoptymalizować za pomocą wczesnego testu if (std::distance(first, last) <= 1) return;(lub dla iteratorów do przodu / dwukierunkowych:) if (first == last || std::next(first) == last) return;.
• w przypadku iteratorów dwukierunkowych powyższy test można połączyć z pętlą w przedziale [first, std::prev(last)), ponieważ ostatni element jest gwarantowanym minimalnym pozostałym elementem i nie wymaga wymiany.

Sortowanie przez wstawianie

Chociaż jest to jeden z elementarnych algorytmów sortowania o O(N²)najgorszym czasie, sortowanie z wstawianiem jest algorytmem z wyboru, gdy dane są prawie posortowane (ponieważ są adaptacyjne ) lub gdy rozmiar problemu jest mały (ponieważ ma niewielki narzut). Z tych powodów oraz ze względu na stabilność , sortowanie wstawiania jest często stosowane jako rekurencyjna podstawa (gdy rozmiar problemu jest niewielki) w celu uzyskania wyższych algorytmów sortowania dziel i zwyciężaj, takich jak sortowanie scalone lub szybkie sortowanie.

Aby zaimplementować insertion_sortw Bibliotece standardowej, kilkakrotnie użyj, std::upper_boundaby znaleźć lokalizację, do której powinien przejść bieżący element, i użyj, std::rotateaby przesunąć pozostałe elementy w górę w zakresie wejściowym:

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));
    }
}

Zauważ, że insertion_sortjuż przetworzony zakres został [first, it)posortowany jako niezmiennik pętli. Sortowanie wstawiania działa również z iteratorami do przodu.

Szczegóły pominięte :

• sortowanie wstawiania można zoptymalizować za pomocą wczesnego testu if (std::distance(first, last) <= 1) return;(lub dla iteratorów do przodu / dwukierunkowych:) if (first == last || std::next(first) == last) return;i pętli w przedziale [std::next(first), last), ponieważ gwarantuje się, że pierwszy element jest na miejscu i nie wymaga obrotu.
• w przypadku dwukierunkowych iteratorów wyszukiwanie binarne w celu znalezienia punktu wstawienia można zastąpić odwrotnym wyszukiwaniem liniowym za pomocą std::find_if_notalgorytmu biblioteki standardowej .

Cztery aktywne przykłady ( C ++ 14 , C ++ 11 , C ++ 98 i Boost , C ++ 98 ) dla poniższego fragmentu:

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();

• W przypadku losowych danych wejściowych daje to O(N²)porównania, ale poprawia się to w O(N)porównaniu do prawie posortowanych danych wejściowych. Wyszukiwanie binarne zawsze wykorzystuje O(N log N)porównania.
• W przypadku małych zakresów wejściowych lepsza lokalizacja pamięci (pamięć podręczna, pobieranie wstępne) wyszukiwania liniowego może również zdominować wyszukiwanie binarne (należy to oczywiście przetestować).

Szybkie sortowanie

Po dokładnym wdrożeniu szybkie sortowanie jest niezawodne i O(N log N)oczekuje się złożoności, ale z O(N²)najgorszą złożonością, która może zostać wywołana przy przeciwnie wybranych danych wejściowych. Gdy sortowanie stabilne nie jest potrzebne, szybkie sortowanie jest doskonałym sortowaniem ogólnego zastosowania.

Nawet w przypadku najprostszych wersji szybkie sortowanie jest nieco bardziej skomplikowane do wdrożenia przy użyciu biblioteki standardowej niż w przypadku innych klasycznych algorytmów sortowania. Poniższe podejście wykorzystuje kilka narzędzi iteratora do zlokalizowania środkowego elementu zakresu wejściowego [first, last)jako osi przestawnej, a następnie użyj dwóch wywołań std::partition(które są O(N)) w celu trójstronnego podziału zakresu wejściowego na segmenty elementów, które są mniejsze niż, równe, i odpowiednio większy niż wybrany element przestawny. Na koniec dwa segmenty zewnętrzne z elementami mniejszymi i większymi niż oś są rekurencyjnie sortowane:

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));
}

Jednak szybkie sortowanie jest dość trudne, aby uzyskać prawidłowe i wydajne, ponieważ każdy z powyższych kroków musi być dokładnie sprawdzony i zoptymalizowany pod kątem kodu poziomu produkcyjnego. W szczególności, dla O(N log N)złożoności, oś przestawna musi skutkować zrównoważonym podziałem danych wejściowych, co nie może być ogólnie gwarantowane dla O(1)osi przestawnej, ale które można zagwarantować, jeśli ustawimy oś jako O(N)medianę zakresu wejściowego.

Szczegóły pominięte :

• powyższa implementacja jest szczególnie podatna na specjalne dane wejściowe, np. ma O(N^2)złożoność dla danych wejściowych „ piszczałki organowej ” 1, 2, 3, ..., N/2, ... 3, 2, 1(ponieważ środek jest zawsze większy niż wszystkie inne elementy).
• mediana-3- punktowa selekcja przestawna z losowo wybranych elementów z zakresu wejściowego chroni przed prawie posortowanymi danymi wejściowymi, dla których w przeciwnym razie złożoność by się pogorszyłaO(N^2).
• Podział na 3 strony (oddzielanie elementów mniejszych, równych i większych niż oś przestawna), jak pokazują dwa wywołania,std::partitionnie jest najbardziej wydajnymO(N)algorytmem do osiągnięcia tego wyniku.
• dla przypadkowych iteratorów dostępu , gwarantowane O(N log N)złożoność można osiągnąć poprzez mediany selekcji obrotu za pomocą std::nth_element(first, middle, last), a następnie rekurencyjnych wywołań quick_sort(first, middle, cmp)i quick_sort(middle, last, cmp).
• ta gwarancja wiąże się jednak z pewnymi kosztami, ponieważ stały współczynnik O(N)złożoności std::nth_elementmoże być droższy niż O(1)złożoności mediany 3-osiowej, po której następuje O(N)wywołanie std::partition(które jest przyjazne dla pamięci podręcznej pojedyncze przejście do przodu dane).

Scal sortowanie

Jeśli korzystanie z O(N)dodatkowej przestrzeni nie ma znaczenia, sortowanie po scaleniu jest doskonałym wyborem: jest to jedyny stabilny O(N log N) algorytm sortowania.

Jest prosty do wdrożenia przy użyciu standardowych algorytmów: użyj kilku narzędzi iteracyjnych, aby zlokalizować środek zakresu wejściowego [first, last)i połączyć dwa rekursywnie posortowane segmenty z 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));
}

Sortowanie po scaleniu wymaga iteratorów dwukierunkowych, przy czym wąskim gardłem jest std::inplace_merge. Pamiętaj, że podczas sortowania list połączonych sortowanie po scaleniu wymaga tylko O(log N)dodatkowego miejsca (do rekurencji). Ten drugi algorytm jest implementowany std::list<T>::sortw bibliotece standardowej.

Sortuj sterty

Sortowanie sterty jest proste do wdrożenia, wykonujeO(N log N)sortowanie na miejscu, ale nie jest stabilne.

Pierwsza pętla, O(N)faza „heapify”, ustawia tablicę w kolejności stosu. Druga pętla, O(N log Nfaza „sortdown”, wielokrotnie wyodrębnia maksimum i przywraca porządek sterty. Biblioteka standardowa sprawia, że ​​jest to wyjątkowo proste:

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));
}

W przypadku, gdy uznają to za „oszustwo” w użyciu std::make_heapi std::sort_heapmożna przejść jeden poziom głębiej i pisać te funkcje się w warunkach std::push_heapi std::pop_heapodpowiednio:

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

Biblioteka standardowa określa zarówno push_heapi pop_heapjako złożoność O(log N). Zauważ jednak, że zewnętrzna pętla w zakresie [first, last)powoduje O(N log N)złożoność make_heap, a std::make_heapma tylko O(N)złożoność. Dla ogólnej O(N log N)złożoności heap_sortnie ma to znaczenia.

Szczegóły pominięte : O(N)wdrożeniemake_heap

Testowanie

Oto cztery przykłady na żywo ( C ++ 14 , C ++ 11 , C ++ 98 i Boost , C ++ 98 ) testujące wszystkie pięć algorytmów na różnych wejściach (nieprzeznaczonych jako wyczerpujące lub rygorystyczne). Zauważ, że ogromne różnice w LOC: C ++ 11 / C ++ 14 potrzebują około 130 LOC, C ++ 98 i Boost 190 (+ 50%), a C ++ 98 ponad 270 (+ 100%).

Kolejny mały i dość elegancki, pierwotnie znaleziony podczas przeglądu kodu . Myślałem, że warto się dzielić.

Liczenie sortuj

Chociaż jest raczej wyspecjalizowany, sortowanie zliczania jest prostym algorytmem sortowania liczb całkowitych i często może być naprawdę szybkie, pod warunkiem, że wartości liczb całkowitych do sortowania nie są zbyt daleko od siebie. Jest to prawdopodobnie idealne rozwiązanie, jeśli kiedykolwiek trzeba posortować zbiór milionów liczb całkowitych o znanej na przykład wartości od 0 do 100.

Aby wdrożyć bardzo proste sortowanie zliczające, które działa zarówno z liczbami całkowitymi ze znakiem, jak i bez znaku, należy znaleźć najmniejsze i największe elementy w kolekcji do sortowania; ich różnica wskaże rozmiar tablicy liczników do przydzielenia. Następnie wykonuje się drugie przejście przez kolekcję, aby policzyć liczbę wystąpień każdego elementu. Na koniec zapisujemy wymaganą liczbę każdej liczby całkowitej z powrotem do oryginalnej kolekcji.

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++);
    }
}

Jest to przydatne tylko wtedy, gdy wiadomo, że zakres liczb całkowitych do sortowania jest niewielki (zwykle nie większy niż rozmiar kolekcji do sortowania), jednak bardziej ogólne liczenie sortowania spowodowałoby spowolnienie w najlepszych przypadkach. Jeśli zakres nie jest znany jako mały, można zastosować inny algorytm, taki jak sortowanie radix , ska_sort lub spreadsort .

Szczegóły pominięte :

• Mogliśmy przekroczyć granice zakresu wartości przyjętych przez algorytm jako parametry, aby całkowicie pozbyć się pierwszego std::minmax_elementprzejścia przez kolekcję. To sprawi, że algorytm będzie jeszcze szybszy, gdy przydaje się inny użyteczny limit zasięgu. (To nie musi być dokładne; przekazanie stałej od 0 do 100 jest wciąż znacznie lepsze niż dodatkowe przejście przez milion elementów, aby dowiedzieć się, że prawdziwe granice wynoszą od 1 do 95. Nawet 0 do 1000 byłoby tego warte; dodatkowe elementy są zapisywane raz zerem i odczytywane raz).

• Dorastanie countsw locie to kolejny sposób na uniknięcie osobnego pierwszego przejścia. Podwojenie countswielkości za każdym razem, gdy ma wzrosnąć, daje zamortyzowany czas O (1) na posortowany element (patrz analiza kosztów wstawiania tabeli skrótów, aby udowodnić, że wzrost wykładniczy jest kluczem). Rosnące na końcu nowe maxjest łatwe dzięki std::vector::resizedodawaniu nowych zerowanych elementów. Wymiana minw locie i wstawianie nowych zerowanych elementów z przodu można wykonać std::copy_backwardpo wyhodowaniu wektora. Następnie, std::fillaby wyzerować nowe elementy.

• countsPętli przyrost jest histogramem. Jeśli dane mogą być bardzo powtarzalne, a liczba pojemników jest niewielka, warto rozwinąć wiele tablic, aby zmniejszyć wąskie gardło zależności między seriami przechowywania / przeładowania do tego samego pojemnika. Oznacza to, że więcej liczy się od zera na początku, a więcej do zapętlenia na końcu, ale powinno być tego warte na większości procesorów w naszym przykładzie milionów od 0 do 100 liczb, szczególnie jeśli dane wejściowe mogą być już (częściowo) posortowane i mają długie serie o tej samej liczbie.

• W powyższym algorytmie używamy min == maxczeku, aby wrócić wcześniej, gdy każdy element ma tę samą wartość (w takim przypadku kolekcja jest sortowana). Zamiast tego można w pełni sprawdzić, czy kolekcja jest już posortowana, jednocześnie wyszukując ekstremalne wartości kolekcji bez marnowania dodatkowego czasu (jeśli w pierwszym przejściu nadal brakuje pamięci z dodatkową pracą związaną z aktualizacją wartości minimalnej i maksymalnej). Jednak taki algorytm nie istnieje w standardowej bibliotece, a pisanie jednego z nich byłoby bardziej nużące niż pisanie samej reszty liczenia. Zostawia się to jako ćwiczenie dla czytelnika.

• Ponieważ algorytm działa tylko z wartościami całkowitymi, można zastosować twierdzenia statyczne, aby zapobiec popełnianiu oczywistych błędów typu. W niektórych kontekstach std::enable_if_tpreferowane może być niepowodzenie podstawienia .

• Podczas gdy współczesne C ++ jest fajne, przyszłe C ++ może być jeszcze fajniejsze: powiązania strukturalne i niektóre części Ranges TS uczynią algorytm jeszcze czystszym.