sortować (C++)
sort to ogólna funkcja w bibliotece standardowej C++ służąca do sortowania porównawczego . Funkcja pochodzi ze standardowej biblioteki szablonów (STL).
Konkretny algorytm sortowania nie jest wymagany przez standard językowy i może różnić się w zależności od implementacji, ale określona jest najgorsza asymptotyczna złożoność funkcji: wywołanie sortowania musi wykonać nie więcej niż O ( N log N ) porównań, gdy jest stosowane do zakres elementów N.
Stosowanie
Funkcja sort jest zawarta w nagłówku <algorithm> biblioteki standardowej C++ i zawiera trzy argumenty : najpierw RandomAccessIterator, na końcu RandomAccessIterator, Compare comp . Tutaj RandomAccessIterator jest typem szablonowym , który musi być iteratorem dostępu swobodnego , a first i last muszą definiować sekwencję wartości, tj. last musi być osiągalny od pierwszego przez wielokrotne zastosowanie operator przyrostu do pierwszego . Trzeci argument, również typu szablonowego, oznacza predykat porównania. Ten predykat porównania musi definiować ściśle słabe uporządkowanie elementów sekwencji do sortowania. Trzeci argument jest opcjonalny; używany jest operator „mniej niż” ( < ), który w C++ może być przeciążony .
Ten przykładowy kod sortuje daną tablicę liczb całkowitych (w porządku rosnącym) i drukuje ją.
0 0
#include <algorytm> #include <iostream> int main () { int tablica [] = { 23 , 5 , -10 , , , 321 , 1 , 2 , 99 , 30 }; std :: sort ( std :: początek ( tablica ), std :: koniec ( tablica
0
)); for ( rozmiar_t i = ; i < std :: rozmiar ( tablica ); ++ ja ) { std :: cout << tablica [ i ] << ' ' ; } std :: cout << '\n' ; }
Ta sama funkcjonalność przy użyciu kontenera wektorów , przy użyciu jego metod begin i end w celu uzyskania iteratorów:
0 0
#include <algorytm> #include <iostream> #include <wektor> int main () { std :: vector < int > vec = { 23 , 5 , -10 , , , 321 , 1 , 2 , 99 , 30 }; std :: sort ( vec . begin (),
0
vec . koniec ()); for ( size_t ja = ; i < vec . size (); ++ ja ) { std :: cout << vec [ i ] << ' ' ; } std :: cout << '\n' ; }
ogólnikowość
sort jest określony ogólnie, dzięki czemu może działać na dowolnym kontenerze o swobodnym dostępie i dowolnym sposobie określenia, czy element x takiego kontenera powinien być umieszczony przed innym elementem y .
sortowanie jest określone ogólnie, nie można go łatwo zastosować do wszystkich problemów z sortowaniem. Szczególny problem, który był przedmiotem niektórych badań, jest następujący:
- Niech A i B będą dwiema tablicami, w których istnieje pewna relacja między elementem A[i] a elementem B[i] dla wszystkich poprawnych indeksów i .
- Sortuj A zachowując relację z B , tj. zastosuj tę samą permutację do B , która sortuje A .
- Wykonaj poprzednie bez kopiowania elementów A i B do nowej tablicy par , sortowania i przenoszenia elementów z powrotem do oryginalnych tablic (co wymagałoby tymczasowego miejsca O ( n ) .
Rozwiązanie tego problemu zaproponował A. Williams w 2002 roku, który zaimplementował niestandardowy typ iteratora dla par tablic i przeanalizował niektóre trudności z poprawną implementacją takiego typu iteratora. Rozwiązanie Williamsa zostało zbadane i udoskonalone przez K. Åhlandera.
Złożoność i implementacje
Standard C++ wymaga, aby wywołanie sort wykonywało porównania O ( N log N ) po zastosowaniu do zakresu N elementów. W poprzednich wersjach C++, takich jak C++03 , wymagana była tylko średnia złożoność O ( N log N ) . Miało to pozwolić na użycie algorytmów takich jak (mediana-of-3) quicksort , które są szybkie w przeciętnym przypadku, a nawet znacznie szybsze niż inne algorytmy, takie jak sortowanie sterty z optymalną złożonością najgorszego przypadku i gdzie rzadko występuje złożoność kwadratowa najgorszego przypadku. Wprowadzenie algorytmów hybrydowych, takich jak introsort , umożliwiło zarówno szybką średnią wydajność, jak i optymalną wydajność w najgorszym przypadku, dlatego wymagania dotyczące złożoności zostały zaostrzone w późniejszych standardach.
Różne implementacje używają różnych algorytmów. Na przykład standardowa biblioteka GNU C++ wykorzystuje 3-częściowy hybrydowy algorytm sortowania: introsort jest wykonywany najpierw (sam introsort jest hybrydą sortowania szybkiego i sortowania sterty), do maksymalnej głębokości określonej przez 2×log 2 n , gdzie n to liczbę elementów, po czym następuje sortowanie przez wstawianie wyniku.
Inne rodzaje sortowania
sortowanie nie jest stabilne: równoważne elementy, które są uporządkowane w jeden sposób przed sortowaniem, mogą być uporządkowane inaczej po sortowaniu. stable_sort zapewnia stabilność wyniku kosztem gorszej wydajności (w niektórych przypadkach), wymagając jedynie czasu quasiliniowego z wykładnikiem 2 – O( n log 2 n ) – jeśli dodatkowa pamięć nie jest dostępna, ale czasu liniowego O( n log n ) jeśli dodatkowe dostępna jest pamięć. Pozwala to na użycie sortowania przez scalanie w miejscu do stabilnego sortowania w miejscu i regularnego sortowania przez scalanie do stabilnego sortowania z dodatkową pamięcią.
Częściowe sortowanie jest realizowane przez częściowe sortowanie , które przyjmuje zakres n elementów i liczbę całkowitą m < n , i porządkuje zakres w taki sposób, że najmniejsze m elementów znajduje się na pierwszych m pozycjach w posortowanej kolejności (pozostawiając pozostałe n − m w pozostałych pozycje, w nieokreślonej kolejności). W zależności od projektu może to być znacznie szybsze niż pełne sortowanie. W przeszłości było to powszechnie realizowane przy użyciu stercie , który zajmuje Θ( n + m log n ) czas najgorszego przypadku. Lepszy algorytm o nazwie quickselsort jest używany w kopenhaskiej implementacji STL, zmniejszając złożoność do Θ( n + m log m ) .
Wybór n - tego elementu jest realizowany przez nth_element , który faktycznie implementuje częściowe sortowanie w miejscu: poprawnie sortuje n- ty element, a także zapewnia, że ten element dzieli tak, że elementy przed nim są mniejsze od niego, a elementy po nim są większy niż to. Istnieje wymóg, że zajmuje to średnio czas liniowy, ale nie ma wymogu najgorszego przypadku; wymagania te są dokładnie spełnione przez quickselect , dla dowolnego wyboru strategii przestawnej.
Niektóre kontenery, między innymi list , udostępniają wyspecjalizowaną wersję sortowania jako funkcję członkowską. Wynika to z faktu, że połączone listy nie mają losowego dostępu (i dlatego nie mogą korzystać ze zwykłej sortowania ); a wersja specjalistyczna zachowuje również wartości, na które wskazują iteratory listy.
Porównanie do qsort
Oprócz funkcji sort standardowa biblioteka C++ zawiera również funkcję qsort ze standardowej biblioteki C. W porównaniu z qsort sortowanie oparte na szablonach jest bardziej bezpieczne pod względem typu, ponieważ nie wymaga dostępu do elementów danych za pośrednictwem niebezpiecznych pustych wskaźników, jak ma to miejsce w przypadku qsort . Ponadto qsort uzyskuje dostęp do funkcji porównania za pomocą wskaźnika funkcji, co wymaga dużej liczby powtarzających się wywołań funkcji, podczas gdy w sort funkcje porównania mogą być wstawiane do niestandardowego kodu wynikowego wygenerowanego dla instancji szablonu. W praktyce kod C++ używający sort jest często znacznie szybszy w sortowaniu prostych danych, takich jak liczby całkowite, niż równoważny kod C używający qsort .