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

Algorytmiczne bloki konstrukcyjne

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() jak również z {[13] } są dostępne tylko w C++11 i nowszych. Do C++98 trzeba je napisać samemu. Są substytuty Z Boost.Zakres w boost::begin() / boost::end(), i z Boost.Użyteczność w boost::next().
• algorytm std::is_sorted jest dostępny tylko dla C++11 i nowszych. W C++98 można to zaimplementować w postaci std::adjacent_find i ręcznie pisanego obiektu funkcji. Boost.Algorytm dostarcza również boost::algorithm::is_sorted jako substytut.
• algorytm std::is_heap jest dostępny tylko dla C++11 i nowszych.

Składniowe gadżety

C++14 zapewnia przezroczyste komparatory z postaci std::less<>, które działają polimorficznie na swoich argumentach. Pozwala to uniknąć konieczności podawania typu iteratora. Może być stosowany w połączeniu z C++11 ' S argumenty domyślnego szablonu funkcji aby utworzyć pojedyncze przeciążenie dla algorytmów sortujących, które przyjmują < jako porównanie i te, które mają zdefiniowany przez użytkownika obiekt funkcji porównawczej.

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

W C++11 można zdefiniować wielokrotnego użytku alias szablonu aby wyodrębnić typ wartości iteratora, który dodaje drobny bałagan do sygnatur 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żyj składni 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 ułatwia owijanie komparatorów zdefiniowanych przez Użytkownika za pomocą polimorficznych lambd (z parametrami auto, które są wydedukowane jak argumenty szablonu funkcji).
• C++11 ma tylko monomorficzne lambdy, które wymagają użycia powyższego aliasu szablonu value_type_t.
W C++98 trzeba albo napisać samodzielny obiekt funkcji, albo skorzystać z verbose std::bind1st / std::bind2nd / std::not1 Typ składni.
• Boost.Bind poprawia to za pomocą boost::bind i_1 / _2 składnia zastępcza.
• C++11 i dalej mają również std::find_if_not, podczas gdy C++98 potrzebuje std::find_if z std::not1 wokół obiektu funkcji.

C++ Style

Nie ma jeszcze ogólnie akceptowalnego stylu C++14. Na dobre i na złe, uważnie śledzę Scotta Meyersa projekt efektywny Nowoczesny C++ Herb Sutter Odnowiony GotW. Stosuję następujące zalecenia stylowe:

• Herb Sutter ' s "prawie zawsze Auto" i Scotta Meyersa "preferuj automatyczne deklaracje od określonego typu" zalecenie, dla którego zwięzłość jest niezrównana, chociaż jej jasność jest czasami sporne.
• Scott Meyers ' s "rozróżnianie () i {} podczas tworzenia obiektów" i konsekwentnie wybierz opcję braced-initialization {} zamiast starej, dobrej inicjalizacji () w nawiasie (aby przejść obok wszystkich najbardziej drażniących problemów w kodzie generycznym).
• Scott Meyers ' s "preferuj deklaracje aliasów od typedefów". W przypadku szablonów i tak jest to koniecznością, a używanie go wszędzie zamiast typedef oszczędza czas i dodaje spójności.
• w niektórych miejscach używam wzorca for (auto it = first; it != last; ++it), aby umożliwić sprawdzanie niezmienników pętli dla już posortowanych podzakresy. W kodzie produkcyjnym użycie while (first != last) i ++first gdzieś wewnątrz pętli może być nieco lepsze.

Sortowanie wyboru

Sortowanie zaznaczenia nie dostosowuje się do danych w żaden sposób, więc jego runtime jest zawsze O(N²). Jednak sortowanie selekcji ma właściwość minimalizującą liczbę swapów. W aplikacjach, w których koszt wymiany przedmiotów jest wysoki, sortowanie selekcji bardzo dobrze może być algorytmem wyboru.

To w tym celu należy użyć biblioteki standardowej, a następnie użyć std::min_element, aby znaleźć pozostały element minimalny iiter_swap, aby zamienić 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_sort ma już przetworzony zakres [first, it) posortowany jako niezmiennik pętli. Minimalne wymagania to Iteratory forward , w porównaniu do iteratorów random access std::sort.

Szczegóły pominięte :

• sortowanie selekcji można zoptymalizować za pomocą wczesnego testu if (std::distance(first, last) <= 1) return; (lub forward / Iteratory dwukierunkowe: if (first == last || std::next(first) == last) return;).
• dla dwukierunkowych iteratorów powyższy test może być połączony z pętlą w przedziale [first, std::prev(last)), ponieważ ostatni element jest gwarantowany jako minimalny element pozostały i nie wymaga wymiany.

Sortowanie wstawiania

Chociaż jest to jeden z elementarnych algorytmów sortowania z O(N²) najgorszym czasem, sortowanie wstawiania jest algorytmem wyboru, gdy dane są prawie posortowane (ponieważ jest adaptacyjne ) lub gdy rozmiar problemu jest mały(ponieważ ma niski narzut). Z tych powodów, a także ze względu na to, że jest stabilny , sortowanie wstawiania jest często używane jako rekurencyjny przypadek podstawowy (gdy rozmiar problemu jest mały) dla algorytmów sortowania o wyższym napowietrznym podziale i podbiciu, takich jak sortowanie scalające lub sortowanie szybkie.

Aby zaimplementować insertion_sort Z biblioteką standardową, wielokrotnie użyj std::upper_bound, aby znaleźć miejsce, w którym bieżący element w tym celu należy użyć [[55]}, aby przesunąć pozostałe elementy w górę zakresu wejściowego: [116]}

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_sort ma już przetworzony zakres [first, it) posortowany jako niezmiennik pętli. Sortowanie wstawiania działa również z iteratorami forward.

Szczegóły pominięte :

• sortowanie wstawiania można zoptymalizować za pomocą wczesnego testu if (std::distance(first, last) <= 1) return; (lub dla iteratorów forward / dwukierunkowych: if (first == last || std::next(first) == last) return;) i pętli nad interwałem [std::next(first), last), ponieważ pierwszy element jest gwarantowane, że będzie na miejscu i nie wymaga obracania.
• dla dwukierunkowych iteratorów , binarne wyszukiwanie w celu znalezienia punktu wstawiania może być zastąpione odwrotnym wyszukiwaniem liniowym przy użyciu algorytmu std::find_if_not biblioteki standardowej.

Cztery przykłady na żywo (C++14, C++11, C++98 i Boost, C++98) dla fragmentu poniżej:

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

• dla losowych wejść daje to O(N²) porównania, ale to poprawia się do O(N) porównania dla prawie posortowanych wejść. Wyszukiwanie binarne zawsze używa porównań O(N log N).
• dla małych zakresów wejściowych, lepsza lokalizacja pamięci (cache, prefetching) wyszukiwania liniowego może również zdominować wyszukiwanie binarne (należy to oczywiście przetestować).

Szybkie sortowanie

Kiedy starannie zaimplementowano, szybkie sortowanie na solidny i ma O(N log N) oczekiwaną złożoność, ale z O(N²) najgorszą złożonością, która może być wywołana za pomocą adversarially wybranych danych wejściowych. Gdy stabilne sortowanie nie jest potrzebne, szybkie sortowanie jest doskonałym sortowaniem ogólnego przeznaczenia.

Nawet dla najprostszych wersji szybkie sortowanie jest nieco bardziej skomplikowane w implementacji przy użyciu biblioteki standardowej niż inne klasyczne algorytmy sortowania. W poniższym podejściu wykorzystuje się kilka narzędzi iteracyjnych do zlokalizowania środkowego elementu . zakres wejściowy [first, last) jako pivot, następnie użyj dwóch wywołań do std::partition (które są O(N)), aby trójkierunkowo podzielić zakres wejściowy na segmenty elementów, które są odpowiednio mniejsze, Równe i większe niż wybrany pivot. Na końcu dwa zewnętrzne segmenty z elementami mniejszymi i większymi od Pivota są sortowane rekurencyjnie:

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 do poprawnego i skutecznego, ponieważ każdy z powyższych kroków musi być dokładnie sprawdzony i zoptymalizowany pod kątem kod poziomu produkcji. W szczególności, dla złożoności O(N log N), pivot musi prowadzić do zbalansowanej partycji danych wejściowych, która nie może być gwarantowana ogólnie dla O(1) pivot, ale która może być gwarantowana, jeśli ustawimy pivot jako medianę zakresu wejściowego.

Szczegóły pominięte :

[118]} powyższa implementacja jest szczególnie podatna na specjalne wejścia, np. ma O(N^2) złożoność dla wejścia" organ pipe " 1, 2, 3, ..., N/2, ... 3, 2, 1 (ponieważ środek jest zawsze większy niż wszystkie inne elementy).
• mediana-of-3 wybór Pivota z losowo wybrane elementy z zakresu wejściowego chroni przed niemal posortowanymi wejściami, dla których złożoność w przeciwnym razie pogorszyłaby się do O(N^2).
• 3-Podział drogi (rozdzielanie elementów mniejszych, równych i większych od Pivota), Jak pokazują dwa wywołania std::partition, nie jest najbardziej efektywny algorytm O(N) do osiągnięcia tego wyniku.
• dla iteratorów dostępu losowego , gwarantowaną złożoność O(N log N) można uzyskać poprzez mediana wyboru pivot za pomocą std::nth_element(first, middle, last), a następnie wywołania rekurencyjne do quick_sort(first, middle, cmp) i quick_sort(middle, last, cmp).
• ta gwarancja jest jednak kosztem, ponieważ stały współczynnik O(N) złożoności std::nth_element może być droższy niż współczynnik O(1) złożoności obrotu Mediany z 3, po którym następuje O(N) wezwanie do std::partition (który jest przyjaznym dla pamięci podręcznej pojedynczym przejściem do przodu nad danymi).

Sortowanie scalające

Jeśli użycie O(N) dodatkowej przestrzeni nie jest problemem, to Sortuj scalanie jest doskonałym wyborem: jest jedynym stabilnym O(N log N) algorytm sortowania.

Jest to proste do zaimplementowania przy użyciu standardowych algorytmów: użyj kilku narzędzi iteracyjnych, aby zlokalizować środek zakresu wejściowego [first, last) i połączyć dwa segmenty sortowane rekurencyjnie 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 scalające wymaga dwukierunkowych iteratorów, wąskim gardłem jest std::inplace_merge. Należy zauważyć, że podczas sortowania list połączonych, sortowanie scalające wymaga tylko O(log N) dodatkowej przestrzeni (dla rekurencji). Ten ostatni algorytm jest zaimplementowany przez std::list<T>::sort w bibliotece standardowej.

Sortowanie sterty

Sortowanie sterty jest prosty w implementacji, wykonuje sortowanie O(N log N) in-place, ale nie jest stabilny.

Pierwsza pętla, O(N) Faza "heapify", umieszcza tablicę w kolejności. Druga pętla, Faza O(N log N) "sortdown", wielokrotnie wyciąga maksimum i przywraca porządek sterty. Biblioteka Standardowa sprawia, że jest to niezwykle 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));
}

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_heap, jak i pop_heap jako złożoność O(log N). Należy jednak pamiętać, że zewnętrzna pętla nad przedziałem [first, last) daje O(N log N) złożoność dla make_heap, podczas gdy std::make_heap ma tylko O(N) złożoność. Dla ogólnej złożoności O(N log N) heap_sort nie ma to znaczenia.

Pominięte szczegóły: O(N) realizacja make_heap

Testowanie

Oto cztery przykłady na żywo (C++14, C++11, C++98 i Boost , C++98) testowanie wszystkich pięciu algorytmów na różnych wejściach (nie ma być wyczerpujące lub rygorystyczne). Zwróć uwagę na ogromne różnice w LOC: C++11/C++14 potrzebują około 130 LOC, C++98 i Boost 190 (+50%) i C++98 ponad 270 (+100%).