En tur i top 5 sorterings algoritmer, Python-kode


Sortering algoritmer kompleksitet’

Sortering er en færdighed, der hver software ingeniør og udvikler har brug for nogle kendskab til. Ikke kun for at bestå kodningsintervie .s, men som en generel forståelse af selve programmeringen., De forskellige sorteringsalgoritmer er et perfekt udstillingsvindue for, hvordan algoritmedesign kan have en så stærk effekt på programmets kompleksitet, hastighed og effektivitet.

lad os tage en rundvisning i de 6 bedste sorteringsalgoritmer og se, hvordan vi kan implementere dem i Python!

Bubble sort er den, der normalt undervises i indledende CS-klasser, da det tydeligt viser, hvordan sort fungerer, mens det er enkelt og let at forstå. Bubble Sorter trin gennem listen og sammenligner tilstødende par af elementer. Elementerne byttes, hvis de er i forkert rækkefølge., Passagen gennem den usorterede del af listen gentages, indtil listen er sorteret. Fordi Bubble sort gentagne gange passerer gennem usorteret del af listen, Det har en worstorst case kompleksitet af O(n2).

Valg Sortere

Udvælgelsen slags er også ganske enkle, men ofte overgår boble slags., Hvis du vælger mellem de to, er det bedst at bare standard ret til udvælgelse sortere. Med Selection sort deler vi vores inputliste / array i to dele: underlisten over varer, der allerede er sorteret, og underlisten over varer, der skal sorteres, der udgør resten af listen. Vi finder først det mindste element i den usorterede underliste og placerer det i slutningen af den sorterede underliste. Således griber vi kontinuerligt det mindste usorterede element og placerer det i sorteret rækkefølge i den sorterede underliste. Denne proces fortsætter iterativt, indtil listen er fuldt sorteret.,

Isætning Sortere

Isætning slags er både hurtigere og godt-nok mere simpelt, end både boble sortere og udvælgelsen slags. Sjovt nok, det er, hvor mange mennesker sortere deres kort, når man spiller et kortspil! På hver loop iteration, indsættelse sort fjerner et element fra arrayet., Derefter finder det sted, hvor dette element hører hjemme i en anden sorteret Matri and og indsætter det der. Det gentager denne proces, indtil der ikke er nogen inputelementer tilbage.

Merge sort

Merge sort er en perfekt elegant eksempel på en Divide and Conquer algoritme., Det enkle bruger de 2 vigtigste trin i sådan en algoritme:

(1) Løbende at opdele usorteret liste, indtil du har N underlister, hvor hver underliste har 1 element, der er “usorteret”, og N er antallet af elementer i det oprindelige array.

(2) gentagne gange fusionere dvs.erobre sublisterne sammen 2 ad gangen for at producere nye sorterede sublister, indtil alle elementer er blevet helt fusioneret til en enkelt sorteret array.,

Hurtig Slags

Hurtig slags er også en divide and conquer algoritme, som merge sort. Selvom det er lidt mere kompliceret, udfører det i de fleste standardimplementeringer betydeligt hurtigere end merge sort og når sjældent sin complexityorst case-kompleksitet af O(n2)., Det har 3 hovedtrin:

(1) Vi vælger først et element, som vi vil kalde pivoten fra arrayet.

(2) Flyt alle elementer, der er mindre end drejeknappen til venstre for drejeknappen; Flyt alle elementer, der er større end drejeknappen til højre for drejeknappen. Dette kaldes partitionsoperationen.

(3) rekursivt anvende ovenstående 2 trin separat til hver af de sub-arrays af elementer med mindre og større værdier end den sidste pivot.,

Skriv et svar

Din e-mailadresse vil ikke blive publiceret. Krævede felter er markeret med *