QuickSort
QuickSort är lite för komplext för att man lätt ska kunna föreställa sig det hos människor, så låt oss komma lite närmare koden. Till att börja med kan vi tänka oss att du har en oordnad lista, eller array, med åtta nummer som du vill ordna.
4 2 13 6 15 12 7 9
Du skulle kunna använda MergeSort, men du har hört att QuickSort generellt sett är snabbare, så du bestämmer dig för att pröva det. Ditt första steg är att välja ett nummer i listan som kallas pivot. Att välja rätt pivotnummer gör hela skillnaden för hur snabbt QuickSort fungerar, och det finns färdiga formler att följa för att välja bra pivotnummer. Men för tillfället håller vi det enkelt och väljer bara det sista numret i matrisen som vårt pivotnummer: 9.
4 2 13 6 15 12 7 9
För att göra nästa steg lättare att följa skapar vi en separator i början av matrisen och representerar den med pundetecknet.
# 4 2 13 6 15 12 7 9
Om vi rör oss från vänster till höger genom vår matris är vårt mål att placera alla tal som är mindre än pivoten (9) till vänster om separatorn och alla tal som är större än (eller lika med) pivoten till höger om separatorn. Vi börjar med det första numret i vår matris: 4. För att flytta det till vänster om separatorn flyttar vi bara upp separatorn ett element:
4 # 2 13 6 15 12 7 9
Vi gör samma sak med nästa tal: 2.
4 2 # 13 6 15 12 7 9
Men sedan kommer vi till 13, som är större än pivottalet 9 och redan står till höger om separatorn. Så vi lämnar det i fred. Därefter kommer vi till 6, som måste gå till vänster om separatorn. Så först byter vi den mot 13 för att få den på plats:
4 2 # 6 13 15 12 7 9
Därefter flyttar vi separatorn förbi den:
4 2 6 # 13 15 12 7 9
Nästa nummer är 15, som redan är till höger om separatorn, så vi låter det vara. Sedan har vi 12. Samma sak. Men 7, vår sista siffra innan vi når pivot, behöver samma typ av hjälp att förflytta sig som 6 gjorde. Så vi byter ut 7 mot 13 för att få det på plats:
4 2 6 # 7 15 12 13 9
Därefter flyttar vi återigen separatorn förbi det:
4 2 6 7 # 15 12 13 9
Slutligt kommer vi till vårt pivotnummer: 9. Enligt samma logik som ovan byter vi ut 15 mot 9 för att få pivotnumret där det ska vara:
4 2 6 7 # 9 12 13 15
Då alla nummer till vänster om 9 nu är mindre än 9, och alla nummer till höger om 9 är större än 9, är vi klara med vår första cykel av QuickSort. Därefter behandlar vi varje uppsättning av fyra nummer på vardera sidan av separatorn som en ny array att tillämpa QuickSort på. Vi ska bespara dig detaljerna, men nästa omgång kommer att ge oss fyra sifferpar som vi enkelt kan tillämpa vår sista omgång av QuickSort på. Slutresultatet blir följande ordnade lista som tog oss mindre tid att generera än vad den skulle ha gjort med den enklare MergeSort:
2 4 6 7 9 12 13 15
Sorteringsalgoritmer som fusklapp
Detta är de vanligaste sorteringsalgoritmerna med några rekommendationer för när de ska användas. Internalisera dessa! De används överallt!
Heap sort: När du inte behöver en stabil sortering och du bryr dig mer om prestanda i värsta fall än i genomsnitt. Den är garanterat O(N log N) och använder O(1) hjälputrymme, vilket innebär att du inte oväntat kommer att få slut på heap- eller stackutrymme vid mycket stora indata.
Introsort: Detta är en snabbsortering som byter till en heap-sortering efter ett visst rekursionsdjup för att komma runt snabbsorteringens O(N²) värsta fall. Det är nästan alltid bättre än en vanlig snabbsortering, eftersom du får det genomsnittliga fallet av en snabbsortering med garanterad O(N log N)-prestanda. Det enda skälet till att använda en heap-sortering i stället för detta är förmodligen i system med mycket begränsat minne där O(log N) stackutrymme är praktiskt taget betydande.
Insertionssortering: När N garanterat är litet, bland annat som grundfall för snabbsortering eller sammanslagningssortering. Även om detta är O(N²) har det en mycket liten konstant och är en stabil sortering.
Bubble sort, selection sort: När du gör något snabbt och smutsigt och av någon anledning inte bara kan använda standardbibliotekets sorteringsalgoritm. Den enda fördelen dessa har jämfört med insertion sort är att de är något lättare att implementera.
Snabbsortering: När du inte behöver en stabil sortering och när genomsnittlig prestanda är viktigare än värsta prestanda. En snabbsortering är O(N log N) i genomsnitt och O(N²) i värsta fall. Ett bra genomförande använder O(log N) extra lagringsutrymme i form av stapelutrymme för rekursion.
Merge sort: När du behöver en stabil O(N log N)-sortering är detta ditt enda alternativ. De enda nackdelarna med den är att den använder O(N) hjälputrymme och har en något större konstant än en snabbsortering. Det finns några sammanslagningar på plats, men AFAIK är de alla antingen inte stabila eller sämre än O(N log N). Till och med O(N log N) in place sorterna har en så mycket större konstant än den gamla vanliga sammanslagningssorteringen att de är mer teoretiska kuriositeter än användbara algoritmer.