Hurtig sortering

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 17. januar 2020; checks kræver 63 redigeringer .

Hurtig sortering
Visualisering af quicksort-algoritmen. Vandrette linjer repræsenterer referenceelementer.
Forfatter	Hoare, Charles Anthony Richard [1]
formål	Sorteringsalgoritme
værste tid	O( n 2 )
Bedste tid	O( n log n ) (normal division) eller O( n ) (tredeling)
Gennemsnitlig tid	O( n log n )
Hukommelsesomkostninger	O( n ) hjælpere O(log n ) hjælpere (Sedgwick 1978)
Mediefiler på Wikimedia Commons

Quick sort , Hoares sort ( eng. quicksort ), ofte kaldet qsort (efter navnet i C-standardbiblioteket ) er en sorteringsalgoritme udviklet af den engelske datalog Tony Hoare under sit arbejde på STU i 1960 .

En af de hurtigste kendte universelle array-sorteringsalgoritmer: gennemsnitlig udveksling ved bestilling af elementer; på grund af tilstedeværelsen af en række mangler i praksis, bruges det normalt med nogle modifikationer. $O(n\log n)$ $n$

Generel beskrivelse

QuickSort er en væsentligt forbedret version af den direkte udvekslingssorteringsalgoritme (varianter af disse er kendt som " Bubble Sort " og " Shaker Sort "), som også er kendt for sin lave effektivitet. Den grundlæggende forskel er, at de størst mulige permutationer laves først, og efter hver gennemgang opdeles elementerne i to uafhængige grupper (hvilket forbedre den mest ineffektive direkte sorteringsmetode resulterede i en af de mest effektive forbedrede metoder).

Den generelle idé med algoritmen er som følger:

Vælg et element fra arrayet, kaldet pivot. Det kan være et hvilket som helst af array-elementerne. Algoritmens rigtighed afhænger ikke af valget af referenceelementet, men i nogle tilfælde kan dets effektivitet stærkt afhænge (se nedenfor).
Sammenlign alle andre elementer med pivoten og omarranger dem i arrayet for at opdele arrayet i tre kontinuerlige segmenter efter hinanden: "elementer mindre end pivoten", "lige" og "større" [2] .
For segmenter med "mindre" og "større" værdier skal du udføre den samme sekvens af operationer rekursivt, hvis længden af segmentet er større end én.

I praksis er arrayet normalt ikke opdelt i tre, men i to dele: for eksempel "mindre reference" og "lige og større"; denne tilgang er generelt mere effektiv, da den forenkler separationsalgoritmen (se nedenfor).

Hoare udviklede denne metode i forhold til maskinoversættelse ; ordbogen blev gemt på magnetbånd , og sorteringen af ordene i den bearbejdede tekst gjorde det muligt at få deres oversættelser på én gang af båndet, uden at spole det tilbage. Algoritmen blev opfundet af Hoare under sit ophold i Sovjetunionen , hvor han studerede computeroversættelse ved Moskva Universitet og udviklede en russisk-engelsk parlør.

Algoritme

Generel sorteringsmekanisme

Quicksort refererer til " divide and conquer "-algoritmer.

Algoritmen består af tre trin:

Vælg et element fra en matrix. Lad os kalde det base.
Opdeling : omarrangering af elementerne i et array, så elementer, der er mindre end pivoten, placeres foran det, og dem, der er større end eller lig, placeres efter det.
Anvend rekursivt de to første trin til de to undergrupper til venstre og højre for pivoten. Rekursion gælder ikke for et array, der kun har ét element eller ingen elementer.

I den mest generelle form ser pseudokode -algoritmen (hvor A er det array, der skal sorteres, og lav og høj er de nedre og øvre grænser for henholdsvis den sorterede sektion af dette array) sådan ud:

algoritme quicksort(A, lav, høj) er hvis lav < høj så p:= partition(A, lav, høj) quicksort(A, lav, p) quicksort(A, p + 1, høj)

Her antages det, at array A sendes ved reference, det vil sige, at sortering sker "på samme sted", og den udefinerede partitionsfunktion returnerer indekset for pivotelementet.

Der er forskellige tilgange til valget af pivotelementet og partitioneringsoperationen, som påvirker algoritmens ydeevne.

Følgende implementering af quicksort er også mulig:

Algoritmen quicksort(A) er, hvis A er tom, returnerer A pivot:= A.pop() (træk sidste eller første element fra array) lA:= A.filter(hvor e <= pivot) (opret array med elementer mindre end pivot) rA := A.filter(hvor e > pivot) (opret array med elementer større end pivot) return quicksort(lA) + [pivot] + quicksort(rA) (retur en matrix bestående af den sorterede venstre side, pivot og sorterede højre side).

I praksis bruges den ikke, men tjener kun til uddannelsesformål, da den bruger ekstra hukommelse, hvilket kan undgås.

Valg af referenceelement

I tidlige implementeringer blev det første element som regel valgt som reference, hvilket reducerede ydeevnen på sorterede arrays. For at forbedre effektiviteten kan det midterste, tilfældige element eller (for store arrays) medianen af det første, midterste og sidste element vælges. [3] Medianen af hele sekvensen er et optimalt omdrejningspunkt, men dens beregning er for tidskrævende at bruge til sortering.

Valg af et pivot med medianen af tre for Lomuto-partitionen:

mid := (lav + høj) / 2 hvis A[mid] < A[lav] skift A[lav] med A[mid] hvis A[høj] < A[lav] skift A[lav] med A[høj] hvis A[høj] < A[midt] skift A[høj] med A[mid] pivot:= A[mid]

Lomuto-partitionering

Denne opdelingsalgoritme blev foreslået af Nico Lomuto [4] og populariseret i bøger af Bentley (Programming Pearls) og Cormen (Introduction to Algorithms). [5] I dette eksempel er det sidste element valgt som pivot. Algoritmen gemmer indekset i variablen i . Hver gang der findes et element, der er mindre end eller lig med pivoten, øges indekset, og elementet indsættes før pivoten. Selvom dette partitioneringsskema er enklere og mere kompakt end Hoare-skemaet, er det mindre effektivt og bruges i tutorials. Kompleksiteten af denne quicksort øges til O ( n2 ), når arrayet allerede er sorteret, eller alle dets elementer er ens. Der er forskellige metoder til at optimere denne sortering: pivotvalgsalgoritmer, ved hjælp af indsættelsessortering på små arrays. I dette eksempel er elementerne i array A sorteret fra lav til høj (inklusive) [5] :

algoritme partition (A, lav, høj) er pivot := A[høj] i := lav for j := lav til høj - 1 gør hvis A[j] ≤ drejer derefter skift A[i] med A[j] i := i + 1 skift A[i] med A[high] returnere i

Sortering af et helt array kan gøres ved at udføre quicksort(A, 1, længde(A)) .

Splitting Hoare

Dette skema bruger to indekser (et i begyndelsen af arrayet, det andet i slutningen), som nærmer sig hinanden, indtil der er et par elementer, hvor det ene er større end pivoten og placeret før det, og det andet er mindre og placeret efter den. Disse elementer er udvekslet. Udvekslingen finder sted, indtil indeksene skærer hinanden. Algoritmen returnerer det sidste indeks. [6] Hoares skema er mere effektivt end Lomutos skema, da der i gennemsnit er tre gange færre udvekslinger (swap) af elementer, og opdeling er mere effektiv, selv når alle elementer er ens. [7] I lighed med Lomutos skema viser dette skema også O ( n2 ) effektivitet, når input-arrayet allerede er sorteret. Sortering ved hjælp af denne ordning er ustabil. Bemærk, at slutpositionen af ankerelementet ikke nødvendigvis er den samme som det returnerede indeks. Pseudokode [5] :

algoritme quicksort(A, lo, hej) er hvis lo < hej da p:= partition(A, lo, hej) quicksort(A, lo, p) quicksort(A, p + 1, hej) algoritme partition (A, lav, høj) er pivot:= A[(lav + høj) / 2] i:= lav j:= høj sløjfe for evigt mens A[i] < pivot i:= i + 1 mens A[j] > drejer j:= j - 1 hvis i >= j så returner j skift A[i++] med A[j--]

Bogen [5] nævner, at en sådan implementering af algoritmen har "mange subtile pointer". Her er en: Valg af et allerede eksisterende element i arrayet som referenceelement kan føre til et call stack overflow på grund af det faktum, at elementnummeret beregnes som et gennemsnit, som ikke er et heltal. Derfor er det mere logisk i denne algoritme at vælge gennemsnitsværdien mellem de indledende og afsluttende elementer som referenceelement:

pivot := (A[lav] + A[høj])/2

Tilbagevendende elementer

For at forbedre ydeevnen med et stort antal identiske elementer i arrayet kan proceduren til at opdele arrayet i tre grupper anvendes: elementer mindre end referencen, lig med den og større end den. (Bentley og McIlroy kalder dette en "fedt partition". Denne partition bruges i qsort- funktionen i Unix 7 [8] ). Pseudokode:

algoritme quicksort(A, lav, høj) er hvis lav < høj så p := pivot(A, lav, høj) venstre, højre := partition(A, p, lav, høj) // returnerer to værdier quicksort (A, lav, venstre) quicksort (A, højre, høj)

Quicksort bruges i sprogstandarden C++, især i sorteringsmetoden for listedatastrukturen.

#include <iostream> #inkluder <liste> int main () { // quicksort std :: liste < int > liste ; const int N = 20 ; for ( int i = 0 ; i < N ; i ++ ) { hvis ( i % 2 == 0 ) liste . push_back ( N - i ); andet liste . push_front ( N - i ); } for ( std :: liste < int >:: iterator it = liste . begynde (); it != liste . slut (); it ++ ) { std :: cout << ( * it ) << " " ; } std :: cout << std :: endl ; liste . sortere (); for ( std :: liste < int >:: iterator it = liste . begynde (); it != liste . slut (); it ++ ) { std :: cout << ( * it ) << " " ; } //hurtig sorteringsafslutning std :: cout << std :: endl ; // sortere større liste . sort ( std :: større < int > ()); for ( std :: liste < int >:: iterator it = liste . begynde (); it != liste . slut (); it ++ ) { std :: cout << ( * it ) << " " ; } std :: cout << std :: endl ; // sortere større ende std :: cin . ignorere (); }

Estimering af kompleksiteten af en algoritme

Det er klart, at operationen med at opdele et array i to dele i forhold til referenceelementet tager tid . Da alle partitioneringsoperationer, der udføres ved den samme rekursionsdybde, behandler forskellige dele af det originale array, hvis størrelse er konstant, vil der i alt også være behov for operationer på hvert rekursionsniveau. Derfor bestemmes den overordnede kompleksitet af algoritmen kun af antallet af divisioner, det vil sige dybden af rekursion. Dybden af rekursionen afhænger til gengæld af kombinationen af inputdata og hvordan pivoten bestemmes. $På)$ $På)$

Bedste sag. I den mest afbalancerede version er arrayet ved hver splitoperation opdelt i to identiske (plus eller minus et element) dele, derfor vil den maksimale rekursionsdybde, hvor størrelserne af de behandlede underarrays når 1, være . Som et resultat heraf ville antallet af sammenligninger udført af quicksort være lig med værdien af det rekursive udtryk , hvilket giver den overordnede kompleksitet af algoritmen .

\log _{2}n

C_{n}=2\cdot C_{{n/2}}+n

O(n\cdot\log _{2}n)

Gennemsnit. Den gennemsnitlige kompleksitet med en tilfældig fordeling af inputdata kan kun estimeres sandsynligt. Først og fremmest skal det bemærkes, at det i virkeligheden ikke er nødvendigt, at pivotelementet deler arrayet i to identiske dele hver gang. For eksempel, hvis der på hvert trin vil være en opdeling i arrays med en længde på 75% og 25% af originalen, vil rekursionsdybden være lig med , og dette giver stadig kompleksitet . Generelt, for ethvert fast forhold mellem venstre og højre del af divisionen, vil kompleksiteten af algoritmen være den samme, kun med forskellige konstanter.

\log _{{4/3}}n

O(n\log n)

Vi vil overveje en "succesfuld" opdeling, således at referenceelementet vil være blandt de centrale 50 % af elementerne i den delte del af arrayet; klart, sandsynligheden for held med en tilfældig fordeling af elementer er 0,5. Med vellykket adskillelse vil størrelserne af de valgte underarrays være mindst 25 % og ikke mere end 75 % af originalen. Da hvert udvalgt underarray også vil have en tilfældig fordeling, gælder alle disse overvejelser for ethvert sorteringstrin og ethvert indledende arrayfragment. En vellykket split giver en rekursionsdybde på ikke mere end . Da sandsynligheden for held er 0,5, vil det tage rekursive kald i gennemsnit at få pivotelementet k gange i midten 50% af arrayet for at få lucky splits. Ved at anvende disse overvejelser kan vi konkludere, at i gennemsnit vil rekursionsdybden ikke overstige , hvilket er lig med A, da der stadig ikke udføres flere operationer på hvert rekursionsniveau , vil den gennemsnitlige kompleksitet være .

\log _{{4/3}}n

k

2\cdot k

2\cdot \log _{{4/3}}n

O(\log n)

På)

O(n\log n)

Værste tilfælde. I den mest ubalancerede version giver hver opdeling to subarrays af størrelserne 1 og , hvilket betyder, at med hvert rekursivt kald vil det større array være 1 kortere end forrige gang. Dette kan ske, hvis enten det mindste eller det største af alle behandlede elementer vælges som referenceelement på hvert trin. Med det enkleste valg af et referenceelement - det første eller sidste i arrayet - vil en sådan effekt blive givet af et allerede sorteret (i direkte eller omvendt rækkefølge) array, for det midterste eller ethvert andet fast element, "worst case-arrayet" ” kan også vælges specielt. I dette tilfælde vil opdelingsoperationer være påkrævet, og den samlede køretid vil være operationer, det vil sige, at sortering vil blive udført i kvadratisk tid. Men antallet af ombytninger og dermed driftstiden er ikke den største ulempe. Værre, i dette tilfælde vil rekursionsdybden under udførelsen af algoritmen nå n, hvilket vil betyde n-fold lagring af returadressen og lokale variabler for array-partitioneringsproceduren. For store værdier af n kan det værste tilfælde føre til hukommelsesudmattelse ( stack overflow ), mens programmet kører.

n-1

n-1

\tekststil \sum _{{i=0}}^{n}(ni)=O(n^{2})

Fordele og ulemper

Fordele:

En af de hurtigste (i praksis) af de generelle interne sorteringsalgoritmer.
Algoritmen er meget kort: husker hovedpunkterne, det er nemt at skrive det "fra hovedet", konstanten ved er lille . $n\log n$
Kræver kun yderligere hukommelse til sit arbejde (uforbedret rekursiv algoritme - i værste tilfælde af hukommelse). $O(1)$ $På)$
Kombinerer godt med caching og virtuelle hukommelsesmekanismer .
Tillader naturlig parallelisering (sortering af allokerede underarrays i parallelle underprocesser).
Tillader effektiv modifikation til sortering efter flere nøgler (især Sedgwick-algoritmen til sortering af strenge): på grund af det faktum, at der under opsplitningsprocessen automatisk allokeres et segment af elementer svarende til referencen, kan dette segment straks sorteres efter det næste nøgle.
Arbejder på linkede lister og andre sekventielle adgangsstrukturer, der tillader effektiv gennemkøring både fra start til slut og fra slut til start.

Fejl:

Forringes kraftigt i hastighed (op til ) i værste fald eller tæt på det, hvilket kan ske med mislykkede inputdata. $O(n^{2})$
En direkte implementering som en funktion med to rekursive kald kan resultere i en stack overflow- fejl, da det i værste fald kan være nødvendigt at lave indlejrede rekursive kald. $På)$
Ustabil .

Forbedringer

Algoritmeforbedringer er hovedsageligt rettet mod at eliminere eller afbøde de ovennævnte ulemper, som et resultat af, at de alle kan opdeles i tre grupper: at gøre algoritmen stabil, eliminere ydeevneforringelse ved et særligt valg af pivotelementet og beskytte mod opkaldsstack overløb på grund af den store rekursionsdybde i tilfælde af mislykkede inputdata.

Problemet med ustabilitet løses ved at udvide nøglen med det indledende indeks for elementet i arrayet. I tilfælde af lighed af hovednøglerne udføres sammenligningen efter indeks, hvilket udelukker muligheden for at ændre den relative position af lige elementer. Denne modifikation er ikke gratis - den kræver en ekstra O(n)-hukommelse og en hel gennemgang gennem arrayet for at gemme de originale indekser.

Hastighedsnedbrydning i tilfælde af et mislykket sæt af inputdata løses i to forskellige retninger: reduktion af sandsynligheden for det værste tilfælde ved et særligt valg af referenceelementet og brugen af forskellige teknikker, der sikrer stabil drift på mislykket input data. For den første retning:

Valg af det midterste element. Eliminerer nedbrydning for forudsorterede data, men efterlader muligheden for tilfældig forekomst eller bevidst valg af et "dårligt" array.
Valg af en median af tre elementer: første, midterste og sidste. Reducerer sandsynligheden for en værst tænkelig hændelse sammenlignet med at vælge det midterste element.
Tilfældigt udvalg. Sandsynligheden for en tilfældig forekomst af worst case bliver forsvindende lille, og bevidst udvælgelse bliver praktisk talt umulig. Den forventede udførelsestid for sorteringsalgoritmen er O( n log n ).

Ulempen ved alle de komplicerede metoder til at vælge referenceelementet er den ekstra overhead; dog er de ikke så store.

For at undgå programfejl på grund af stor rekursionsdybde kan følgende metoder bruges:

Når en uønsket rekursionsdybde er nået, skift til sortering efter andre metoder, der ikke kræver rekursion. Et eksempel på denne tilgang er Introsort- algoritmen eller nogle implementeringer af quicksort i STL -biblioteket . Det kan ses, at algoritmen er meget velegnet til denne form for modifikation, da den på hvert trin giver dig mulighed for at vælge et kontinuerligt segment af det originale array beregnet til sortering, og metoden, hvormed dette segment vil blive sorteret, påvirker ikke behandlingen af de resterende dele af arrayet.
Ændring af algoritmen, der eliminerer én gren af rekursion: i stedet for at kalde opdelingsproceduren rekursivt for begge fundne subarrays, efter at arrayet er opdelt, foretages det rekursive kald kun for det mindre underarray, og det større behandles i en sløjfe i samme procedure opkald . Fra et effektivitetssynspunkt er der i det gennemsnitlige tilfælde praktisk talt ingen forskel: overhead for et ekstra rekursivt opkald og til at organisere en sammenligning af længderne af underarrays og en sløjfe er omtrent den samme rækkefølge. Men rekursionsdybden vil under ingen omstændigheder overstige , og i værste tilfælde af en degenereret division vil den generelt ikke være mere end 2 - al bearbejdning vil finde sted i cyklussen af det første rekursionsniveau. Brug af denne metode vil ikke redde dig fra et katastrofalt fald i ydeevnen, men der vil ikke være noget stak overløb. $\log _{2}n$
Opdel arrayet ikke i to, men i tre dele [9] .

Se også

Liste over sorteringsalgoritmer

Noter

↑ Hoare C. A. R. Algoritme 64: Quicksort // Commun . ACM - [New York] : Association for Computing Machinery , 1961. - Vol. 4, Iss. 7. - S. 321. - ISSN 0001-0782 ; 1557-7317 - doi:10.1145/366622.366644
↑ Det er klart, efter en sådan permutation, for at opnå et sorteret array, vil det ikke være nødvendigt at flytte nogen af elementerne mellem de resulterende segmenter, det vil sige, at det vil være nok at sortere de "mindre" og "større" segmenter som uafhængige arrays.
↑ Sedgewick, Robert Algoritmer i C : Grundlæggende, datastrukturer, sortering, søgning, del 1-4 . — 3. — Pearson Education, 1998. - ISBN 978-81-317-1291-7 .
↑ John Bentley. Programmering af perler . — Addison-Wesley Professional , 1999.
↑ 1 2 3 4 Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Quicksort // Algorithms: construction and analysis = Introduction to Algorithms / Ed. I. V. Krasikova. - 3. udg. — M. : Williams, 2013. — S. 170–190. — ISBN 5-8459-1794-8 .
↑ Hoare, C. a. R. Quicksort // Computer Journal : journal. - 1962. - 1. januar ( bind 5 , nr. 1 ). - S. 10-16 . — ISSN 0010-4620 . - doi : 10.1093/comjnl/5.1.10 .
↑ Quicksort-opdeling: Hoare vs. Lomuto . cs.stackexchange.com . Hentet: 3. august 2015. (ubestemt)
↑ Bentley, John L.; McIlroy, M. Douglas. Engineering a sort function (engelsk) // Software—Praksis og erfaring. - 1993. - Bd. 23 , nr. 11 . - S. 1249-1265 . - doi : 10.1002/spe.4380231105 .
↑ Dual Pivot Quicksort . Dato for adgang: 8. december 2015. Arkiveret fra originalen 4. marts 2016. (ubestemt)

Litteratur

Levitin A. V. Kapitel 4. Nedbrydningsmetode: Quicksort // Algoritmer. Introduktion til udvikling og analyse - M . : Williams , 2006. - S. 174-179. — 576 s. — ISBN 978-5-8459-0987-9
Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Kapitel 7. Quicksort // Algoritmer: konstruktion og analyse = Introduktion til algoritmer / Ed. I. V. Krasikova. - 2. udg. - M. : Williams, 2005. - S. 198-219. — ISBN 5-8459-0857-4 .

Links

Animeret sammenligning af sorteringsalgoritmer
Gengivere: [1] , [2] , [3]
Dynamisk visualisering 7 Open Source-sorteringsalgoritmer

Sorteringsalgoritmer
Teori	Kompleksitet O notation Ordreforhold Sorter typer bæredygtige Indre Ekstern
Udveksling	boble Omrøring Dværge Hurtig Kam Sortering lige-ulige Bitvis
Valg	Valg Pyramideformet Glat
indsætter	indsætter shella træ
fusion	fusion
Ingen sammenligninger	Tæller blok
hybrid	introsort Timsort
Andet	Topologisk netværk biton
upraktisk	Bogosort Stooge sort pandekage langsom