introduktion
Nogle gange kan data, Vi gemmer eller henter i en applikation, have ringe eller ingen ordre. Vi er muligvis nødt til at omarrangere dataene for at behandle dem korrekt eller effektivt bruge dem. I årenes løb har computerforskere skabt mange sorteringsalgoritmer til at organisere data.
i denne artikel vil vi se på populære sorteringsalgoritmer, forstå, hvordan de virker og kode dem i Python. Vi vil også sammenligne, hvor hurtigt de sortere elementer i en liste.,
for enkelhed ville algoritmeimplementeringer sortere lister over tal i stigende rækkefølge., Du er naturligvis fri til at tilpasse dem til dine behov
Hvis du gerne vil lære om en bestemt algoritme, kan du springe til det her:
- Boble Form
- Valg Form
- Isætning Form
- Merge sort
- Bunke Form
- Hurtig Form
- Sortering i Python
Boble Sortere
Denne enkle sorterings-algoritme iterates over en liste, at sammenligne elementer i par og bytter dem, indtil de større elementer “boble op” til slutningen af listen, og de mindre elementer ophold på “bunden”.,
forklaring
Vi begynder med at sammenligne de to første elementer på listen. Hvis det første element er større end det andet element, bytter vi dem. Hvis de allerede er i orden, forlader vi dem som de er. Vi flytter derefter til det næste par elementer, sammenligner deres værdier og bytter efter behov. Denne proces fortsætter til det sidste par elementer på listen.
efter at have nået slutningen af listen, gentager den denne proces for hvert element. Dette er dog meget ineffektivt. Hvad hvis der kun skal foretages en enkelt s ?ap i arrayet?, Hvorfor skulle vi stadig gentage, selvom det n^2 gange, selvom det allerede er sorteret?for at optimere algoritmen skal vi naturligvis stoppe den, når den er færdig med at sortere, ellers vil den revurdere et allerede sorteret array mange gange.
hvordan ville vi vide, at vi er færdige med at sortere? Hvis varerne var i orden, ville vi ikke skulle bytte nogen. Så når vi bytter værdier, sætter vi et flag til True for at gentage sorteringsprocessen. Hvis der ikke forekom s .aps, forbliver flaget False, og algoritmen stopper.,
implementering
med optimeringen kan vi implementere Bubble Sort i Python som følger:
algoritmen kører i en while loop, kun bryde, når ingen elementer byttes. Vi indstiller swapped til True i begyndelsen for at sikre, at algoritmen kører mindst en gang.
tidskompleksitet
i værste fald (når listen er i omvendt rækkefølge), skal denne algoritme bytte hvert enkelt element i arrayet., Vores swapped flag ville være indstillet til True på hver iteration.
derfor, hvis vi har n – elementer på vores liste, ville vi have N-iterationer pr.
Selection Sort
denne algoritme inddeler listen i to dele: sorteret og usorteret. Vi fjerner kontinuerligt det mindste element i det usorterede segment på listen og tilføjer det til det sorterede segment.,
forklaring
i praksis behøver vi ikke at oprette en ny liste for de sorterede elementer, hvad vi gør er at behandle den venstre del af listen som det sorterede segment. Vi søger derefter hele listen efter det mindste element og bytter det med det første element.
nu ved vi, at det første element i listen er sorteret, vi får det mindste element i de resterende elementer og bytter det med det andet element. Dette gentages, indtil det sidste punkt på listen er det resterende element, der skal undersøges.,
implementering
Vi ser, at nåri øges, skal vi kontrollere mindre elementer.
tidskompleksitet
Vi kan nemt få tidskompleksiteten ved at undersøge for sløjfer i Valgsorteringsalgoritmen. For en liste med n-elementer gentager den ydre sløjfe n gange.
den indre sløjfe gentager n-1, når jeg er lig med 1, og derefter n-2 som jeg er lig med 2 og så videre.
mængden af sammenligninger er(n - 1) + (n - 2) + ... + 1, hvilket giver valg Sorter en tidskompleksitet af O(n^2).,
Indsætningssortering
ligesom Markeringssortering segmenter denne algoritme listen i sorterede og usorterede dele. Det gentager sig over det usorterede segment og indsætter elementet, der ses, i den korrekte placering af den sorterede liste.
forklaring
Vi antager, at det første element i listen er sorteret. Vi går derefter til det næste element, lad os kalde det x. Hvis x er større end det første element, forlader vi som det er., Hvis x er mindre, kopierer vi værdien af det første element til den anden position og indstiller derefter det første element tilx.
Som vi gå til andre dele af usorteret segment, vi hele tiden flytte større elementer i sorteret segmentet op på listen, indtil vi støder på et element, der er mindre end x eller nå slutningen af den sorterede segment, og derefter placere x i den korrekte position.
Hvis du gerne vil læse en detaljeret, dedikeret artikel til indsættelsessortering, har vi dig dækket!,
implementering
tidskompleksitet
i værste fald vil et array blive sorteret i omvendt rækkefølge. Den ydre for loop i indsættelses sorteringsfunktion gentager altid n-1 gange.
Heap Sort
denne populære sorteringsalgoritme, som indsættelses-og Markeringssorteringer, segmenter listen i sorterede og usorterede dele. Det konverterer usorteret segment af listen til en bunke datastruktur, så vi effektivt kan bestemme det største element.,
forklaring
Vi begynder med at omdanne listen til en maks.bunke – et binært træ, hvor det største element er rodnoden. Vi placerer derefter dette emne til slutningen af listen. Vi genopbygger derefter vores Ma. – bunke, som nu har en mindre værdi, og placerer den nye største værdi før det sidste punkt på listen.
Vi gentager denne proces med at opbygge bunken, indtil alle noder er fjernet.
Hvis du gerne vil læse en detaljeret, dedikeret artikel til Heap Sort, har vi dig dækket!,
Gennemførelsen
Vi vil skabe en hjælper, funktion heapify for at gennemføre denne algoritme:
Tid Kompleksitet
Lad os først se på den tid, kompleksitet heapify funktion. I værste fald er det største element aldrig rodelementet, hvilket medfører et rekursivt opkald til heapify. Mens rekursive opkald kan virke skræmmende dyre, husk at vi arbejder med et binært træ.
Visualiser et binært træ med 3 elementer, det har en højde på 2., Visualiser nu et binært træ med 7 elementer, det har en højde på 3. Træet vokser logaritmisk til n.funktionen heapify krydser det Træ I O(log(n)) tid.
funktionenheap_sort gentages over array n gange. Derfor er den samlede tidskompleksitet af Heapsorteringsalgoritmen O(nlog (n)).
Flet Sort
denne divide and con .uer-algoritme opdeler en liste i halvdelen og fortsætter med at opdele listen med 2, indtil den kun har entalelementer.,
tilstødende elementer bliver sorterede par, derefter sorterede par fusioneres og sorteres med andre par så godt. Denne proces fortsætter, indtil vi får en sorteret liste med alle elementerne i den usorterede inputliste.
forklaring
Vi deler rekursivt listen i halvdelen, indtil vi har lister med størrelse en. Vi fusionerer derefter hver halvdel, der blev delt, og sorterer dem i processen.
sortering sker ved at sammenligne de mindste elementer i hver halvdel. Det første element i hver liste er de første, der skal sammenlignes. Hvis første halvdel begynder med en mindre værdi, tilføjer vi det til den sorterede liste., Vi sammenligner derefter den anden mindste værdi af første halvdel med den første mindste værdi af anden halvdel.
hver gang vi vælger den mindre værdi i begyndelsen af en halv, flytter vi indekset for hvilket element der skal sammenlignes med en.
Hvis du gerne vil læse en detaljeret, dedikeret artikel til Merge Sort, har vi dig dækket!
implementering
Bemærk, atmerge_sort() – funktionen, i modsætning til de tidligere sorteringsalgoritmer, returnerer en ny liste, der er sorteret, snarere end at sortere den eksisterende liste.,derfor kræver Merge Sort plads til at oprette en ny liste med samme størrelse som inputlisten.
tidskompleksitet
lad os først se på merge – funktionen. Det tager to lister, og gentager n gange, hvor n er størrelsen af deres kombinerede input.
merge_sort funktionen opdeler det givne array i 2, og sorterer rekursivt underarrayerne. Som input bliver genvundet er halvdelen af, hvad der blev givet, ligesom binære træer dette gør den tid, det tager at behandle vokse logaritmisk til n.,
derfor er den samlede tidskompleksitet af flet Sorteringsalgoritmen O(nlog(n)).
hurtig sortering
denne opdelings-og erobringsalgoritme er den oftest anvendte sorteringsalgoritme, der er dækket af denne artikel. Når den er konfigureret korrekt, er den ekstremt effektiv og kræver ikke den ekstra pladsfusionssortering. Vi partitionerer listen omkring et pivotelement og sorterer værdier omkring pivoten.
forklaring
hurtig sortering begynder ved at opdele listen – plukke en værdi af listen, der vil være i sin sorterede sted. Denne værdi kaldes en pivot., Alle elementer, der er mindre end pivoten, flyttes til venstre. Alle større elementer flyttes til højre.ved at vide, at pivoten er på det retmæssige sted, sorterer vi rekursivt værdierne omkring pivoten, indtil hele listen er sorteret.
Hvis du gerne vil læse en detaljeret, dedikeret artikel til hurtig sortering, har vi dig dækket!
implementering
tidskompleksitet
det værst tænkelige scenarie er, når det mindste eller største element altid vælges som pivot. Dette ville skabe partitioner af størrelse n-1, forårsager rekursive opkald n-1 gange., Dette fører os til en complexityorst case tid kompleksitet af O(n^2).
selvom dette er et forfærdeligt værste tilfælde, er Quickuick Sort stærkt brugt, fordi det er gennemsnitlig tidskompleksitet er meget hurtigere. Mens funktionen partition bruger indlejret while sløjfer, gør den sammenligninger på alle elementer i arrayet for at lave sine S .aps. Som sådan har det en tidskompleksitet af O(n).
med en god pivot vil Quickuick Sort-funktionen partitionere arrayet i halvdele, der vokser logaritmisk med n. derfor er den gennemsnitlige tidskompleksitet for Quickuick Sort-algoritmen O(nlog(n)).,
Pythons indbyggede sorteringsfunktioner
selvom det er gavnligt at forstå disse sorteringsalgoritmer, vil du i de fleste Python-projekter sandsynligvis bruge de sorteringsfunktioner, der allerede findes på sproget.,
Vi kan ændre vores liste for at have det indhold, der er sorteret med de sort() metode:
apples_eaten_a_day = apples_eaten_a_day.sort()print(apples_eaten_a_day) # , Eller vi kan bruge den sorted() funktion til at oprette en ny sorteret liste:
apples_eaten_a_day_2 = sorted_apples = sorted(apples_eaten_a_day_2)print(sorted_apples) # De begge sortere i stigende rækkefølge, men du kan nemt sortere i faldende rækkefølge ved at sætte reverse flag til True:
i Modsætning til sorterings-algoritme funktioner, vi har skabt, er begge disse funktioner kan sortere lister af elementer og klasser., Funktionen sorted() kan sortere ethvert iterbart objekt, og det inkluderer lister, strenge, tupler, ordbøger, sæt og brugerdefinerede iteratorer, du kan oprette.
disse sorteringsfunktioner implementerer Tim-Sorteringsalgoritmen, en algoritme inspireret af Merge-sortering og indsættelses-sortering.
Hastighedssammenligninger
for at få en ID.om, hvor hurtigt de udfører, genererer vi en liste med 5000 tal mellem 0 og 1000. Vi så tid, hvor lang tid det tager for hver algoritme til at fuldføre. Dette gentages 10 gange, så vi mere pålideligt kan etablere et mønster af ydeevne.,
dette var resultaterne, tiden er i sekunder:
Du får forskellige værdier, hvis du selv konfigurerer testen, men de observerede mønstre skal være de samme eller lignende. Bubble Sort er den langsomste den værste udøver af alle algoritmerne. Selvom det er nyttigt som en introduktion til sortering og algoritmer, er det ikke egnet til praktisk brug.
Vi bemærker også, at Quickuick Sort er meget hurtig, næsten dobbelt så hurtig som Merge Sort, og det behøver ikke så meget plads til at køre. Husk, at vores partition var baseret på det midterste element på listen, forskellige partitioner kunne have forskellige resultater.,
da Indsætningssortering udfører meget mindre sammenligninger end Markeringssortering, er implementeringerne normalt hurtigere, men i disse kørsler er Markeringssorteringen lidt hurtigere.
Indsætningssorter gør meget mere S .aps end Markeringssortering. Hvis bytte værdier tager betydeligt mere tid end at sammenligne værdier, ville dette “modsatte” resultat være plausibelt.
Vær opmærksom på miljøet, når du vælger din sorteringsalgoritme, da det vil påvirke ydeevnen.
konklusion
sorteringsalgoritmer giver os mange måder at bestille vores data på., Vi kiggede på 6 forskellige algoritmer-Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Heap Sort, Quickuick Sort – og deres implementeringer i Python.
mængden af sammenligning og S .aps algoritmen udfører sammen med miljøet koden kører er centrale determinanter for ydeevne. I rigtige Python-applikationer anbefales det, at vi holder fast i de indbyggede Python-sorteringsfunktioner for deres fleksibilitet på input og hastighed.