Snabb sortering

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 17 januari 2020; kontroller kräver 63 redigeringar .

Snabb sortering
Visualisering av quicksort-algoritmen. Horisontella linjer representerar referenselement.
Författare	Hoare, Charles Anthony Richard [1]
ändamål	Sorteringsalgoritm
värsta tiden	O( n 2 )
Lämpligast tid	O( n log n ) (normal division) eller O( n ) (tripartition)
Snittid	O( n log n )
Minneskostnad	O( n ) helpers O(log n ) helpers (Sedgwick 1978)
Mediafiler på Wikimedia Commons

Quick sort , Hoares sort ( eng. quicksort ), ofta kallad qsort (efter namnet i C-standardbiblioteket ) är en sorteringsalgoritm som utvecklades av den engelske datavetaren Tony Hoare under sitt arbete på STU 1960 .

En av de snabbaste kända universella array-sorteringsalgoritmerna: i genomsnitt utbyte vid beställning av element; på grund av förekomsten av ett antal brister i praktiken, används det vanligtvis med vissa modifieringar. $O(n\log n)$ $n$

Allmän beskrivning

QuickSort är en avsevärt förbättrad version av direktväxlingssorteringsalgoritmen (varianter av dessa är kända som " Bubble Sort " och " Shaker Sort "), som också är känd för sin låga effektivitet. Den grundläggande skillnaden är att de största möjliga permutationerna görs först, och efter varje pass delas elementen in i två oberoende grupper (vilket förbättrade den mest ineffektiva direktsorteringsmetoden resulterade i en av de mest effektiva förbättrade metoderna).

Den allmänna idén med algoritmen är följande:

Välj ett element från arrayen, kallat pivot. Det kan vara vilket som helst av arrayelementen. Algoritmens riktighet beror inte på valet av referenselement, men i vissa fall kan dess effektivitet starkt bero (se nedan).
Jämför alla andra element med pivoten och arrangera om dem i arrayen så att arrayen delas upp i tre kontinuerliga segment efter varandra: "element mindre än pivoten", "lika" och "större" [2] .
För segment med "mindre" och "större" värden, utför samma sekvens av operationer rekursivt om segmentets längd är större än ett.

I praktiken är arrayen vanligtvis inte uppdelad i tre, utan i två delar: till exempel "mindre referens" och "lika och större"; detta tillvägagångssätt är generellt sett mer effektivt, eftersom det förenklar separationsalgoritmen (se nedan).

Hoare utvecklade denna metod i förhållande till maskinöversättning ; ordboken lagrades på magnetband , och sorteringen av orden i den bearbetade texten gjorde det möjligt att få översättningarna på en gång av bandet, utan att spola tillbaka den. Algoritmen uppfanns av Hoare under hans vistelse i Sovjetunionen , där han studerade datoröversättning vid Moskvas universitet och utvecklade en rysk-engelsk parlör.

Algoritm

Allmän sorteringsmekanism

Quicksort hänvisar till " dela och erövra " algoritmer.

Algoritmen består av tre steg:

Välj ett element från en array. Låt oss kalla det bas.
Dela : omarrangera elementen i en array så att element mindre än pivoten placeras före den, och de som är större än eller lika placeras efter den.
Applicera rekursivt de två första stegen på de två subarrayerna till vänster och höger om pivoten. Rekursion gäller inte för en array som bara har ett element eller inga element.

I den mest allmänna formen ser pseudokodalgoritmen (där A är arrayen som ska sorteras och låg och hög är de nedre respektive övre gränserna för den sorterade sektionen av denna array) ut så här:

algoritm quicksort(A, låg, hög) är om låg < hög då p:= partition(A, låg, hög) quicksort(A, låg, p) quicksort(A, p + 1, hög)

Här antas det att matrisen A skickas genom referens, det vill säga sortering sker "på samma plats", och den odefinierade partitionsfunktionen returnerar indexet för pivotelementet.

Det finns olika tillvägagångssätt för valet av pivotelementet och partitioneringsoperationen som påverkar algoritmens prestanda.

Följande implementering av quicksort är också möjlig:

Algoritmen quicksort (A) är om A är tom returnera A pivot:= A.pop() (dra sista eller första elementet från array) lA:= A.filter(där e <= pivot) (skapa array med element mindre än pivot) rA := A.filter(där e > pivot) (skapa array med element större än pivot) return quicksort(lA) + [pivot] + quicksort(rA) (retur en array bestående av den sorterade vänstersidan, pivoten och sorterade högersidan).

I praktiken används det inte, utan tjänar endast för utbildningsändamål, eftersom det använder extra minne, vilket kan undvikas.

Val av referenselement

I tidiga implementeringar valdes som regel det första elementet som referens, vilket minskade prestandan på sorterade arrayer. För att förbättra effektiviteten kan det mellersta, slumpmässiga elementet eller (för stora arrayer) medianen för de första, mellersta och sista elementen väljas. [3] Medianen för hela sekvensen är en optimal pivot, men dess beräkning är för tidskrävande att använda vid sortering.

Välja en pivot med medianen av tre för Lomuto-partitionen:

mid := (låg + hög) / 2 om A[mid] < A[låg] byt ut A[låg] med A[mid] om A[hög] < A[låg] byt ut A[låg] med A[hög] om A[hög] < A[mid] byt ut A[hög] med A[mid] pivot:= A[mid]

Lomuto-partitionering

Denna partitioneringsalgoritm föreslogs av Nico Lomuto [4] och populariserades i böcker av Bentley (Programming Pearls) och Cormen (Introduction to Algorithms). [5] I det här exemplet är det sista elementet valt som pivot. Algoritmen lagrar indexet i variabeln i . Varje gång ett element hittas som är mindre än eller lika med pivoten, inkrementeras indexet och elementet infogas före pivoten. Även om detta partitioneringsschema är enklare och mer kompakt än Hoare-schemat, är det mindre effektivt och används i tutorials. Komplexiteten för denna snabbsort ökar till O ( n2 ) när matrisen redan är sorterad eller alla dess element är lika. Det finns olika metoder för att optimera denna sortering: pivotvalsalgoritmer, med hjälp av insättningssortering på små arrayer. I det här exemplet är elementen i array A sorterade från låg till hög (inklusive) [5] :

algoritmpartition (A, låg, hög) är pivot := A[hög] jag := låg för j := låg till hög - 1 gör om A[j] ≤ pivoterar då byt ut A[i] med A[j] i := i + 1 byt ut A[i] med A[high] returnera i

Att sortera en hel array kan göras genom att göra quicksort(A, 1, length(A)) .

Klyvning Hoare

Detta schema använder två index (ett i början av arrayen, det andra i slutet), som närmar sig varandra tills det finns ett par element där det ena är större än pivoten och placerat före det, och det andra är mindre och ligger efter den. Dessa element är utbytta. Utbytet sker tills indexen skär varandra. Algoritmen returnerar det sista indexet. [6] Hoares schema är mer effektivt än Lomutos schema, eftersom det i genomsnitt finns tre gånger färre utbyten (swap) av element, och partitionering är effektivare även när alla element är lika. [7] I likhet med Lomutos schema visar detta schema också O ( n2 ) effektivitet när inmatningsmatrisen redan är sorterad . Sortering med detta schema är instabil. Observera att ändpositionen för ankarelementet inte nödvändigtvis är detsamma som det returnerade indexet. Pseudokod [5] :

algoritm quicksort(A, lo, hej) är om lo < hej då p:= partition(A, lo, hej) quicksort(A, lo, p) quicksort(A, p + 1, hej) algoritmpartition (A, låg, hög) är pivot:= A[(låg + hög) / 2] i:= låg j:= hög slinga för alltid medan A[i] < pivot i:= i + 1 medan A[j] > pivot j:= j - 1 om i >= j returnera j byt ut A[i++] med A[j--]

Boken [5] nämner att en sådan implementering av algoritmen har "många subtila poäng". Här är en: Att välja ett redan existerande element i arrayen som ett referenselement kan leda till ett överflöde av anropsstack på grund av att elementnumret beräknas som ett medelvärde, vilket inte är ett heltal. Därför är det mer logiskt i denna algoritm att välja medelvärdet mellan de initiala och slutliga elementen som referenselement:

pivot := (A[låg] + A[hög])/2

Återkommande element

För att förbättra prestandan med ett stort antal identiska element i arrayen, kan proceduren för att dela arrayen i tre grupper tillämpas: element mindre än referensen, lika med den och större än den. (Bentley och McIlroy kallar detta en "fat partition". Denna partition används i qsort- funktionen i Unix 7 [8] ). Pseudokod:

algoritm quicksort(A, låg, hög) är om låg < hög då p := pivot(A, låg, hög) vänster, höger := partition(A, p, låg, hög) // returnerar två värden quicksort (A, låg, vänster) quicksort(A, höger, hög)

Quicksort används i språkstandarden C++, särskilt i sorteringsmetoden för listdatastrukturen.

#include <iostream> #inkludera <lista> int main () { // snabbsort std :: lista < int > lista ; const int N = 20 ; för ( int i = 0 ; i < N ; i ++ ) { if ( i % 2 == 0 ) lista . push_back ( N - i ); annan lista . push_front ( N - i ); } for ( std :: list < int >:: iterator it = list . begin (); it != list . end (); it ++ ) { std :: cout << ( * it ) << " " ; } std :: cout << std :: endl ; lista . sortera (); for ( std :: list < int >:: iterator it = list . begin (); it != list . end (); it ++ ) { std :: cout << ( * it ) << " " ; } //snabb sorteringsslut std :: cout << std :: endl ; // sortera större lista . sort ( std :: större < int > ()); for ( std :: list < int >:: iterator it = list . begin (); it != list . end (); it ++ ) { std :: cout << ( * it ) << " " ; } std :: cout << std :: endl ; // sortera större slut std :: cin . ignorera (); }

Uppskattning av komplexiteten hos en algoritm

Det är tydligt att operationen att dela upp en array i två delar i förhållande till referenselementet tar tid . Eftersom alla partitioneringsoperationer som utförs med samma rekursionsdjup bearbetar olika delar av den ursprungliga arrayen, vars storlek är konstant, totalt kommer operationer också att krävas på varje rekursionsnivå. Därför bestäms den övergripande komplexiteten av algoritmen endast av antalet divisioner, det vill säga djupet av rekursion. Djupet av rekursionen beror i sin tur på kombinationen av indata och hur pivoten bestäms. $På)$ $På)$

Bästa fall. I den mest balanserade versionen, vid varje delad operation, är matrisen uppdelad i två identiska (plus eller minus ett element) delar, därför kommer det maximala rekursionsdjupet vid vilket storlekarna på de behandlade subarrayerna når 1 att vara . Som ett resultat av detta skulle antalet jämförelser som utförs av quicksort vara lika med värdet på det rekursiva uttrycket , vilket ger den övergripande komplexiteten för algoritmen .

\log _{2}n

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

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

Medel. Den genomsnittliga komplexiteten med en slumpmässig fördelning av indata kan endast uppskattas probabilistiskt. Först och främst bör det noteras att det i verkligheten inte är nödvändigt att pivotelementet delar upp arrayen i två identiska delar varje gång. Till exempel, om det i varje steg kommer att finnas en uppdelning i arrayer med en längd på 75% och 25% av originalet, kommer rekursionsdjupet att vara lika med , och detta ger fortfarande komplexitet . I allmänhet, för varje fixerat förhållande mellan de vänstra och högra delarna av divisionen, kommer komplexiteten hos algoritmen att vara densamma, bara med olika konstanter.

\log _{{4/3}}n

O(n\log n)

Vi kommer att överväga en "framgångsrik" uppdelning så att referenselementet kommer att vara bland de centrala 50% av elementen i den delade delen av arrayen; uppenbarligen är sannolikheten för tur med en slumpmässig fördelning av element 0,5. Med lyckad separation kommer storlekarna på de valda subarrayerna att vara minst 25 % och inte mer än 75 % av originalet. Eftersom varje vald subarray också kommer att ha en slumpmässig fördelning, gäller alla dessa överväganden för alla sorteringssteg och vilket initialt arrayfragment som helst. En lyckad split ger ett rekursionsdjup på högst . Eftersom sannolikheten för tur är 0,5, kommer det att krävas rekursiva anrop i genomsnitt för att få pivotelementet k gånger i mitten 50 % av arrayen för att få lucky splits. Genom att tillämpa dessa överväganden kan vi dra slutsatsen att i genomsnitt rekursionsdjupet inte kommer att överstiga , vilket är lika med A eftersom inga fler operationer fortfarande utförs på varje nivå av rekursion , kommer den genomsnittliga komplexiteten att vara .

\log _{{4/3}}n

k

2\cdot k

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

O(\log n)

På)

O(n\log n)

Värsta fall. I den mest obalanserade versionen ger varje uppdelning två subarrays av storlekarna 1 och , vilket betyder att med varje rekursivt anrop kommer den större matrisen att vara 1 kortare än föregående gång. Detta kan hända om antingen det minsta eller det största av alla bearbetade element väljs som referenselement i varje steg. Med det enklaste valet av ett referenselement - det första eller sista i arrayen - kommer en sådan effekt att ges av en redan sorterad (i direkt eller omvänd ordning) array, för mitten eller något annat fast element, "worst case-arrayen ” kan också väljas speciellt. I det här fallet kommer uppdelningsoperationer att krävas, och den totala körtiden kommer att vara operationer, det vill säga sortering kommer att utföras i kvadratisk tid. Men antalet byten och därmed driftstiden är inte dess största nackdel. Ännu värre, i detta fall kommer rekursionsdjupet under exekveringen av algoritmen att nå n, vilket kommer att innebära en n-faldig besparing av returadressen och lokala variabler för arraypartitioneringsproceduren. För stora värden på n kan i värsta fall leda till minnesutmattning ( stack overflow ) medan programmet körs.

n-1

n-1

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

Fördelar och nackdelar

Fördelar:

En av de snabbaste (i praktiken) av de allmänna interna sorteringsalgoritmerna.
Algoritmen är mycket kort: genom att komma ihåg huvudpunkterna är det lätt att skriva det "från huvudet", konstanten vid är liten . $n\log n$
Kräver endast ytterligare minne för sitt arbete (oförbättrad rekursiv algoritm - i värsta fall av minne). $O(1)$ $På)$
Kombinerar bra med caching och virtuella minnesmekanismer .
Tillåter naturlig parallellisering (sortering av allokerade delmatriser i parallella delprocesser).
Tillåter effektiv modifiering för sortering med flera nycklar (särskilt Sedgwick-algoritmen för sortering av strängar): på grund av det faktum att ett segment av element lika med referensen automatiskt allokeras under uppdelningsprocessen, kan detta segment omedelbart sorteras efter nästa nyckel.
Fungerar på länkade listor och andra sekventiella åtkomststrukturer som möjliggör effektiv genomgång både från början till slut och från slut till start.

Brister:

Degraderar kraftigt i hastighet (upp till ) i värsta fall eller nära det, vilket kan hända med misslyckade indata. $O(n^{2})$
En direkt implementering som en funktion med två rekursiva anrop kan resultera i ett stackoverflow- fel, eftersom det i värsta fall kan behöva göra kapslade rekursiva anrop. $På)$
Instabil .

Förbättringar

Algoritmförbättringar är huvudsakligen inriktade på att eliminera eller mildra ovanstående nackdelar, som ett resultat av vilka alla kan delas in i tre grupper: att göra algoritmen stabil, eliminera prestandaförsämring genom ett speciellt val av pivotelementet och skydda mot anropsstack spill på grund av det stora rekursionsdjupet vid misslyckade indata.

Problemet med instabilitet löses genom att utöka nyckeln med det initiala indexet för elementet i arrayen. I fallet med likhet mellan huvudnycklarna utförs jämförelsen av index, vilket utesluter möjligheten att ändra den relativa positionen för lika element. Denna modifiering är inte gratis - den kräver ett extra O(n)-minne och en hel passage genom arrayen för att spara de ursprungliga indexen.

Hastighetsförsämring i fallet med en misslyckad uppsättning indata löses i två olika riktningar: att minska sannolikheten för att det värsta fallet inträffar genom ett speciellt val av referenselementet och användningen av olika tekniker som säkerställer stabil drift vid misslyckad inmatning data. För den första riktningen:

Välja mittelementet. Eliminerar försämring för försorterade data, men lämnar möjligheten för slumpmässig förekomst eller avsiktligt val av en "dålig" array.
Välja en median av tre element: första, mitten och sista. Minskar sannolikheten för en värsta händelse jämfört med att välja mellanelementet.
Slumpmässigt urval. Sannolikheten för en slumpmässig förekomst av det värsta fallet blir försvinnande liten, och medvetet urval blir praktiskt taget omöjligt. Den förväntade exekveringstiden för sorteringsalgoritmen är O( n log n ).

Nackdelen med alla de komplicerade metoderna för att välja referenselementet är den extra omkostnaden; dock är de inte så bra.

För att undvika programfel på grund av stort rekursionsdjup kan följande metoder användas:

När ett oönskat rekursionsdjup uppnås, byt till sortering med andra metoder som inte kräver rekursion. Ett exempel på detta tillvägagångssätt är Introsort- algoritmen, eller några implementeringar av quicksort i STL- biblioteket . Det kan ses att algoritmen är mycket väl lämpad för denna typ av modifiering, eftersom den i varje steg låter dig välja ett kontinuerligt segment av den ursprungliga arrayen avsedd för sortering, och metoden med vilken detta segment kommer att sorteras påverkar inte bearbetningen av de återstående delarna av arrayen.
Modifiering av algoritmen som eliminerar en gren av rekursion: istället för att anropa delningsproceduren rekursivt för båda hittade subarrayerna efter att arrayen har delats, görs det rekursiva anropet endast för den mindre underarrayen, och den större bearbetas i en loop inom samma procedursamtal . Ur effektivitetssynpunkt är det i genomsnittsfallet praktiskt taget ingen skillnad: overheaden för ett ytterligare rekursivt anrop och för att organisera en jämförelse av längderna på subarrayer och en loop är ungefär samma ordning. Men rekursionsdjupet kommer under inga omständigheter att överstiga , och i värsta fall av en degenererad division kommer det i allmänhet inte att vara mer än 2 - all bearbetning kommer att ske i cykeln av den första nivån av rekursion. Att använda den här metoden kommer inte att rädda dig från en katastrofal nedgång i prestanda, men det kommer inte att finnas något stackspill. $\log _{2}n$
Dela upp arrayen inte i två, utan i tre delar [9] .

Se även

Lista över sorteringsalgoritmer

Anteckningar

↑ Hoare C. A. R. Algoritm 64: Quicksort // Commun . ACM - [New York] : Association for Computing Machinery , 1961. - Vol. 4, Iss. 7. - P. 321. - ISSN 0001-0782 ; 1557-7317 - doi:10.1145/366622.366644
↑ Uppenbarligen, efter en sådan permutation, för att erhålla en sorterad array, kommer det inte att vara nödvändigt att flytta något av elementen mellan de resulterande segmenten, det vill säga, det kommer att vara tillräckligt att sortera de "mindre" och "större" segmenten som oberoende arrayer.
↑ Sedgewick, Robert Algoritmer i C : Grunder, datastrukturer, sortering, sökning, del 1-4 . — 3. — Pearson Education, 1998. - ISBN 978-81-317-1291-7 .
↑ John Bentley. Programmering Pärlor . — Addison-Wesley Professional , 1999.
↑ 1 2 3 4 Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Quicksort // Algoritmer: konstruktion och analys = Introduktion till algoritmer / Ed. I. V. Krasikova. - 3:e uppl. — M. : Williams, 2013. — S. 170–190. — ISBN 5-8459-1794-8 .
↑ Hoare, C. a. R. Quicksort // Datorjournalen _ : journal. - 1962. - 1 januari ( vol. 5 , nr 1 ). - S. 10-16 . — ISSN 0010-4620 . - doi : 10.1093/comjnl/5.1.10 .
↑ Quicksort-partitionering: Hoare vs. Lomuto . cs.stackexchange.com . Hämtad: 3 augusti 2015. (obestämd)
↑ Bentley, John L.; McIlroy, M. Douglas. Konstruera en sortsfunktion (engelska) // Programvara—övning och erfarenhet. - 1993. - Vol. 23 , nr. 11 . - P. 1249-1265 . - doi : 10.1002/spe.4380231105 .
↑ Snabbsortering med dubbel pivot . Tillträdesdatum: 8 december 2015. Arkiverad från originalet 4 mars 2016. (obestämd)

Litteratur

Levitin A. V. Kapitel 4. Nedbrytningsmetod: Quicksort // Algoritmer. Introduktion till utveckling och analys - M . : Williams , 2006. - S. 174-179. — 576 sid. — ISBN 978-5-8459-0987-9
Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Kapitel 7. Quicksort // Algorithms: construction and analysis = Introduction to Algorithms / Ed. I. V. Krasikova. - 2:a uppl. - M. : Williams, 2005. - S. 198-219. — ISBN 5-8459-0857-4 .

Länkar

Animerad jämförelse av sorteringsalgoritmer
Renderare: [1] , [2] , [3]
Dynamisk visualisering 7 sorteringsalgoritmer med öppen källkod

Sorteringsalgoritmer
Teori	Komplexitet O notation Orderförhållande Sorteringstyper hållbar Inre Extern
Utbyta	bubbla Omrörning Dvärgar Snabb Hårkam Sortering jämnt-udda Bitvis
Val	Val Pyramidformad Slät
Insatser	Insatser shella träd
fusion	fusion
Inga jämförelser	Räkning blockera
hybrid	introsort Timsort
Övrig	Topologiska nätverk biton
opraktisk	Bogosort Stooge sort pannkaka långsam