sortera (C++)
sort är en generisk funktion i C++ Standard Library för att göra jämförelsesortering . Funktionen har sitt ursprung i Standard Template Library (STL).
Den specifika sorteringsalgoritmen är inte mandat av språkstandarden och kan variera mellan olika implementeringar, men funktionens värsta fall asymptotiska komplexitet specificeras: ett anrop att sortera får inte utföra mer än O ( N log N ) jämförelser när det tillämpas på en intervall av N element.
Användande
Sorteringsfunktionen är inkluderad från <algorithm> -huvudet i C++ Standard Library och har tre argument : RandomAccessIterator först, RandomAccessIterator sist , Compare comp . Här RandomAccessIterator en malltyp som måste vara en direktåtkomstiterator och först och sist måste definiera en sekvens av värden, dvs. sist måste vara tillgänglig från första genom upprepad applicering av inkrementoperatorn till first . Det tredje argumentet, också av malltyp, betecknar ett jämförelsepredikat. Detta jämförelsepredikat måste definiera en strikt svag ordning på elementen i sekvensen som ska sorteras. Det tredje argumentet är valfritt; används operatorn "mindre än" ( < ), som kan vara överbelastad i C++.
Detta kodexempel sorterar en given array av heltal (i stigande ordning) och skriver ut den.
0 0
0
#inkludera <algoritm> #inkludera <iostream> int main () { int array [] = { 23 , 5 , -10 , , , 321 , 1 , 2 , 99 , 30 }; std :: sort ( std :: start ( array ), std :: end ( array )); for ( size_t i = ; i < std :: storlek ( array ); ++ i ) { std :: cout << array [ i ] << ' ' ; } std :: cout << '\n' ; }
Samma funktionalitet med en vektorbehållare , med dess start- och slutmetoder för att få iteratorer:
0 0
0
#inkludera <algoritm> #inkludera <iostream> #inkludera <vektor> int main () { std :: vektor < int > vec = { 23 , 5 , -10 , , , 321 , 1 , 2 , 99 , 30 }; std :: sort ( vec . start (), vec . end ()); for ( size_t i = ; i < vec . size ( ); ++ i ) { std :: cout << vec [ i ] << ' ' ; } std :: cout << '\n' ; }
Genericitet
sort specificeras generiskt, så att den kan fungera på alla slumpmässiga behållare och alla sätt att bestämma att ett element x i en sådan behållare ska placeras före ett annat element y .
Även om det är generiskt specificerat är sortering inte lätt att tillämpa på alla sorteringsproblem. Ett särskilt problem som har varit föremål för någon studie är följande:
- Låt A och B vara två arrayer, där det finns någon relation mellan elementet A[i] och elementet B[i] för alla giltiga index i .
- Sortera A samtidigt som relationen med B bibehålls , dvs tillämpa samma permutation på B som sorterar A .
- Gör det föregående utan att kopiera elementen i A och B till en ny array av par , sortera och flytta tillbaka elementen till de ursprungliga arrayerna (vilket skulle kräva O ( n ) tillfälligt utrymme).
En lösning på detta problem föreslogs av A. Williams 2002, som implementerade en anpassad iteratortyp för par av arrayer och analyserade några av svårigheterna med att korrekt implementera en sådan iteratortyp. Williams lösning studerades och förfinades av K. Åhlander.
Komplexitet och implementeringar
C++-standarden kräver att ett anrop att sortera utför O ( N log N ) jämförelser när det tillämpas på ett intervall av N element. I tidigare versioner av C++, såsom C++03 , krävdes endast medelkomplexitet för att vara O ( N log N ) . Detta var för att tillåta användningen av algoritmer som (median-av-3) quicksort , som är snabba i genomsnittsfallet, faktiskt betydligt snabbare än andra algoritmer som heap-sortering med optimal värsta fallets komplexitet, och där värsta fallet kvadratisk komplexitet förekommer sällan. Införandet av hybridalgoritmer som introsort tillät både snabb medelprestanda och optimal värsta tänkbar prestanda, och därmed skärptes komplexitetskraven i senare standarder.
Olika implementeringar använder olika algoritmer. GNU Standard C++-biblioteket , till exempel , använder en 3-delad hybridsorteringsalgoritm: introsort utförs först (introsort i sig är en hybrid av quicksort och heapsortering), till ett maximalt djup som ges av 2×log 2n , där n är antalet element, följt av en infogningssortering på resultatet.
Andra sorters sortering
sorteringen är inte stabil: likvärdiga element som ordnas åt ett håll före sortering kan ordnas annorlunda efter sortering. stable_sort säkerställer resultatstabilitet på bekostnad av sämre prestanda (i vissa fall), kräver endast kvasilinjär tid med exponent 2 – O( n log 2 n ) – om ytterligare minne inte är tillgängligt, men linjär tid O( n log n ) om ytterligare minne minne är tillgängligt. Detta möjliggör användning av in-place merge-sortering för in-place-stabil sortering och vanlig merge-sortering för stabil sortering med extra minne.
Partiell sortering implementeras av partial_sort , som tar ett intervall på n element och ett heltal m < n , och ordnar om intervallet så att de minsta m elementen är i de första m positionerna i sorterad ordning (lämnar de återstående n − m i de återstående positioner, i någon ospecificerad ordning). Beroende på design kan detta vara betydligt snabbare än komplett sortering. Historiskt sett har detta vanligtvis implementerats med en heap -baserad algoritm som tar Θ( n + m log n ) värsta tänkbara tid. En bättre algoritm som kallas quickselsort används i Köpenhamns STL-implementering, vilket sänker komplexiteten till Θ( n + m log m ) .
Val av det n: te elementet implementeras av nth_element , som faktiskt implementerar en partiell sortering på plats: det sorterar det n :te elementet korrekt och säkerställer också att detta element partitionerar så att element före det är mindre än det, och element efter det är större än det. Det finns kravet att detta tar linjär tid i genomsnitt, men det finns inget värsta tänkbart krav; dessa krav uppfylls exakt med snabbval , för alla val av pivotstrategi.
Vissa behållare, bland dem listan , tillhandahåller specialiserad version av sortering som en medlemsfunktion. Detta beror på att länkade listor inte har slumpmässig åtkomst (och därför inte kan använda den vanliga sorteringsfunktionen ); och den specialiserade versionen bevarar också de värden som listiteratorer pekar på.
Jämförelse med qsort
Förutom sortering innehåller C++-standardbiblioteket även qsort -funktionen från C-standardbiblioteket . Jämfört med qsort är den mallade sorteringen mer typsäker eftersom den inte kräver åtkomst till dataobjekt via osäkra void -pekare, som qsort gör. Dessutom qsort tillgång till jämförelsefunktionen med hjälp av en funktionspekare, vilket kräver ett stort antal upprepade funktionsanrop, medan jämförelsefunktioner kan infogas i den anpassade objektkoden som genereras för en mallinstansiering. I praktiken är C++-kod som använder sorter ofta betydligt snabbare på att sortera enkla data som heltal än motsvarande C-kod med qsort .