introduktion
Ibland kan data som vi lagrar eller hämtar i ett program ha liten eller ingen ordning. Vi kan behöva omorganisera data för att korrekt bearbeta den eller effektivt använda den. Genom åren har Dataforskare skapat många sorteringsalgoritmer för att organisera data.
i den här artikeln ska vi ta en titt på populära sorteringsalgoritmer, förstå hur de fungerar och koda dem i Python. Vi jämför också hur snabbt de sorterar objekt i en lista.,
För enkelhetens skull skulle algoritmimplementeringar vara att sortera listor med siffror i stigande ordning., Självklart är du fri att anpassa dem till dina behov
om du vill lära dig om en specifik algoritm kan du hoppa till det här:
- Bubble Sort
- Selection Sort
- Insertion Sort
- Merge Sort
- Heap Sort
- Quick Sort
- sortering i Python
Bubble Sort
denna enkla sorteringsalgoritm itererar över en lista, jämföra element i par och byta dem tills de större elementen ”bubbla upp” till slutet av listan, och de mindre elementen stanna på ”botten”.,
förklaring
vi börjar med att jämföra de två första elementen i listan. Om det första elementet är större än det andra elementet byter vi dem. Om de redan är i ordning lämnar vi dem som det är. Vi flyttar sedan till nästa par element, jämför deras värden och byta vid behov. Denna process fortsätter till det sista paret av objekt i listan.
När du når slutet av listan upprepar den denna process för varje objekt. Men detta är mycket ineffektivt. Vad händer om bara en enda swap behöver göras i matrisen?, Varför skulle vi fortfarande iterera om det n^2 gånger, även om det redan är sorterade?
självklart, för att optimera algoritmen, måste vi stoppa den när den är klar sortering, annars kommer det att omvärdera en redan sorterad array många gånger.
hur vet vi att vi är klara med sorteringen? Om objekten var i ordning skulle vi inte behöva byta några. Så när vi byter värden ställer vi in en flagga till True för att upprepa sorteringsprocessen. Om inga swappar inträffade skulle flaggan förbli False och algoritmen stoppas.,
implementering
med optimeringen kan vi implementera bubbla sortera i Python enligt följande:
algoritmen körs i enwhile slinga, bara bryta när inga objekt byts. Vi ställer inswapped tillTrue I början för att säkerställa att algoritmen körs minst en gång.
tidskomplexitet
i värsta fall (när listan är i omvänd ordning) skulle denna algoritm behöva byta varje enskild post i matrisen., Vårswapped flagga skulle ställas in påTrue på varje iteration.
därför, om vi har n element i vår lista, skulle vi ha n iterationer per objekt – således bubbla sortens tid komplexitet är O (n^2).
Selection Sort
denna algoritm delar listan i två delar: sorterad och osorterad. Vi tar kontinuerligt bort det minsta elementet i det osorterade segmentet i listan och lägger det till det sorterade segmentet.,
förklaring
i praktiken behöver vi inte skapa en ny lista för de sorterade elementen, det vi gör är att behandla den vänstra delen av listan som det sorterade segmentet. Vi söker sedan hela listan efter det minsta elementet och byter det med det första elementet.
nu vet vi att det första elementet i listan är sorterat, vi får det minsta elementet i de återstående objekten och byter det med det andra elementet. Detta upprepas tills den sista punkten i förteckningen är den återstående delen som ska granskas.,
implementering
Vi ser att somi ökar måste vi kontrollera mindre objekt.
tidskomplexitet
Vi kan enkelt få tidskomplexiteten genom att undersökafor – slingorna i Urvalssorteringsalgoritmen. För en lista med n-element itererar den yttre slingan n gånger.
den inre slingan itererar n-1 när jag är lika med 1, och sedan n-2 som jag är lika med 2 och så vidare.
mängden jämförelser är(n - 1) + (n - 2) + ... + 1, vilket ger Val Sortera en tid komplexitet O(n^2).,
insättningssortering
som Urvalssortering segmenterar denna algoritm listan i sorterade och osorterade delar. Det itererar över det osorterade segmentet och infogar elementet som ses i rätt position för den sorterade listan.
förklaring
vi antar att det första elementet i listan är sorterat. Vi går sedan till nästa element, låt oss kalla det x. Omx är större än det första elementet vi lämnar som det är., Omx är mindre kopierar vi värdet för det första elementet till det andra läget och ställer sedan in det första elementet tillx.
När vi går till andra delar av det osorterade segmentet flyttar vi kontinuerligt större element i det sorterade segmentet upp listan tills vi stöter på ett element som är mindre än x eller når slutet av det sorterade segmentet och placerar sedan x I rätt position.
om du vill läsa en detaljerad, dedikerad artikel för insättningssortering, har vi dig täckt!,
implementering
tidskomplexitet
i värsta fall skulle en array sorteras i omvänd ordning. Den yttrefor loop I Insättningssorteringsfunktionen itererar alltid n-1 gånger.
Heap Sort
denna populära sorteringsalgoritm, som insättnings-och Urvalssorter, delar listan i sorterade och osorterade delar. Det konverterar osorterade segmentet av listan till en hög datastruktur, så att vi effektivt kan bestämma det största elementet.,
förklaring
vi börjar med att omvandla listan till en Max Heap – ett binärt träd där det största elementet är rotnoden. Vi placerar sedan objektet till slutet av listan. Vi bygger sedan upp vår Max Heap som nu har ett mindre värde och placerar det nya största värdet före det sista objektet i listan.
vi itererar denna process för att bygga högen tills alla noder tas bort.
om du vill läsa en detaljerad, dedikerad artikel för Heap Sort, har vi dig täckt!,
implementering
vi skapar en hjälpfunktionheapify för att implementera denna algoritm:
tidskomplexitet
låt oss först titta på tidskomplexiteten hos funktionenheapify. I värsta fall är det största elementet aldrig rotelementet, vilket orsakar ett rekursivt samtal till heapify. Medan rekursiva samtal kan verka skrämmande dyra, kom ihåg att vi arbetar med ett binärt träd.
visualisera ett binärt träd med 3 element, det har en höjd av 2., Visualisera nu ett binärt träd med 7 element, det har en höjd av 3. Trädet växer logaritmiskt till n.funktionen heapify korsar det trädet i o(log(n)) tid.
funktionenheap_sort itererar över arrayen n gånger. Därför är den övergripande tidskomplexiteten hos heap-Sorteringsalgoritmen O(nlog (n)).
Merge Sort
den här divide and conquer-algoritmen delar upp en lista i hälften och delar upp listan med 2 tills den bara har singulära element.,
intilliggande element blir sorterade par, sedan sorteras par slås samman och sorteras med andra par också. Denna process fortsätter tills vi får en sorterad lista med alla element i den osorterade inmatningslistan.
förklaring
vi delar upp listan rekursivt i hälften tills vi har listor med storlek ett. Vi sammanfogar sedan varje halva som delades, sorterar dem i processen.
sortering görs genom att jämföra de minsta elementen i varje hälft. Det första elementet i varje lista är det första som ska jämföras. Om den första halvan börjar med ett mindre värde lägger vi till det i den sorterade listan., Vi jämför sedan det näst minsta värdet av den första halvan med det första minsta värdet av den andra halvan.
varje gång vi väljer det mindre värdet i början av en halv flyttar vi indexet för vilket objekt som behöver jämföras med en.
om du vill läsa en detaljerad, dedikerad artikel för Merge Sort, har vi dig täckt!
implementering
Observera att funktionenmerge_sort(), till skillnad från tidigare sorteringsalgoritmer, returnerar en ny lista som sorteras, snarare än att sortera den befintliga listan.,
därför kräver Merge Sort utrymme för att skapa en ny lista av samma storlek som inmatningslistan.
tidskomplexitet
låt oss först titta på funktionenmerge. Det tar två listor, och itererar n gånger, där n är storleken på deras kombinerade ingång.
funktionenmerge_sort delar upp sin givna array i 2 och sorterar rekursivt undermatriserna. Som ingången recursed är hälften av vad som gavs, som binära träd detta gör den tid det tar att bearbeta växa logaritmiskt till n.,
därför är den totala tidskomplexiteten för den sammanfogade Sorteringsalgoritmen O(nlog (n)).
Quick Sort
denna divide and conquer-algoritm är den vanligaste sorteringsalgoritmen som omfattas av den här artikeln. När den är korrekt konfigurerad är den extremt effektiv och kräver inte extra utrymme Merge Sorteringsanvändningar. Vi partitionerar listan runt ett pivotelement, sorterar värden runt pivot.
förklaring
snabb sortering börjar genom att partitionera listan – plocka ett värde på listan som kommer att vara på sin sorterade plats. Detta värde kallas en pivot., Alla element som är mindre än pivot flyttas till vänster. Alla större element flyttas till höger.
att veta att pivot är på rätt plats sorterar vi rekursivt värdena runt pivot tills hela listan sorteras.
om du vill läsa en detaljerad, dedikerad artikel för snabb sortering, har vi dig täckt!
implementering
tidskomplexitet
det värsta scenariot är när det minsta eller största elementet alltid väljs som pivot. Detta skulle skapa partitioner av storlek n-1, vilket orsakar rekursiva samtal n-1 gånger., Detta leder oss till en värsta fall tid komplexitet O (n^2).
Även om det här är ett hemskt värsta fall, används Quick Sort kraftigt eftersom det är genomsnittlig tidskomplexitet är mycket snabbare. Medan partition funktionen använder kapsladewhile loopar, gör det jämförelser på alla delar av matrisen för att göra sina swappar. Som sådan har den en tidskomplexitet av O (n).
med en bra pivot skulle Quick Sort-funktionen partitionera matrisen i halvor som växer logaritmiskt med n. därför är den genomsnittliga tidskomplexiteten hos Quick Sort-algoritmen O(nlog (n)).,
Pythons inbyggda sorteringsfunktioner
även om det är fördelaktigt att förstå dessa sorteringsalgoritmer, skulle du i de flesta Python-projekt förmodligen använda sorteringsfunktionerna som redan finns på språket.,
vi kan ändra vår lista så att dess innehåll sorteras medsort() metod:
apples_eaten_a_day = apples_eaten_a_day.sort()print(apples_eaten_a_day) # eller så kan vi använda funktionensorted() för att skapa en ny sorterad lista:
apples_eaten_a_day_2 = sorted_apples = sorted(apples_eaten_a_day_2)print(sorted_apples) # de sorterar båda i stigande ordning, men du kan enkelt sortera i fallande ordning genom att ställa inreverse flagga tillTrue:
till skillnad från de sorteringsalgoritmfunktioner vi skapade kan båda dessa funktioner sortera listor över tuplar och klasser., Funktionensorted() kan sortera vilket objekt som helst och som innehåller-listor, strängar, tuplar, ordböcker, uppsättningar och anpassade iteratorer du kan skapa.
dessa sorteringsfunktioner implementerar Tim-Sorteringsalgoritmen, en algoritm inspirerad av Sammanfogningssortering och Infogningssortering.
hastighet jämförelser
för att få en uppfattning om hur snabbt de utför, vi genererar en lista med 5000 nummer mellan 0 och 1000. Vi tar då tid hur lång tid det tar för varje algoritm att slutföra. Detta upprepas 10 gånger så att vi mer tillförlitligt kan skapa ett mönster av prestanda.,
dessa var resultaten, tiden är i sekunder:
du skulle få olika värden om du ställer in testet själv, men de observerade mönstren ska vara desamma eller liknande. Bubble Sort är den långsammaste den värsta utövande av alla algoritmer. Även om det är användbart som en introduktion till sortering och algoritmer, är det inte lämpligt för praktisk användning.
vi märker också att Quick Sort är mycket snabb, nästan dubbelt så snabbt som Merge Sort och det skulle inte behöva så mycket utrymme att köra. Minns att vår partition baserades på mittenelementet i listan, olika partitioner kan ha olika resultat.,
eftersom insättningssortering utför mycket mindre jämförelser än Urvalssortering är implementeringarna vanligtvis snabbare men i dessa körningar är Urvalssorteringen något snabbare.
Insättningssorter gör mycket mer swappar än Urvalssortering. Om byte av värden tar upp betydligt mer tid än att jämföra värden, skulle detta ”motsatta” resultat vara rimligt.
Var uppmärksam på miljön när du väljer sorteringsalgoritm, eftersom det kommer att påverka prestanda.
slutsats
sorteringsalgoritmer ger oss många sätt att beställa våra data., Vi tittade på 6 olika algoritmer-bubbla Sortera, val Sortera, insättning Sortera, sammanfoga Sortera, Heap Sortera, snabb Sort-och deras implementeringar i Python.
mängden jämförelse och swappar algoritmen utför tillsammans med miljön koden körs är viktiga bestämningsfaktorer för prestanda. I verkliga Python-applikationer rekommenderas att vi håller fast vid de inbyggda Python-sorteringsfunktionerna för deras flexibilitet på ingång och hastighet.