en rundtur i topp 5 sorteringsalgoritmer med Python-kod

sorteringsalgoritmer’

sortering är en färdighet som varje mjukvaruingenjör och utvecklare behöver viss kunskap om. Inte bara för att klara kodningsintervjuer utan som en allmän förståelse för programmering själv., De olika sorteringsalgoritmerna är en perfekt presentation av hur algoritmdesign kan ha en så stark effekt på programkomplexitet, hastighet och effektivitet.

låt oss ta en rundtur i topp 6 sorteringsalgoritmer och se hur vi kan implementera dem i Python!

Bubble sort är den som vanligtvis lärs ut i inledande CS-klasser eftersom det tydligt visar hur sorteringen fungerar samtidigt som den är enkel och lätt att förstå. Bubbla Sortera steg genom listan och jämför intilliggande par av element. Elementen byts om de är i fel ordning., Passet genom den osorterade delen av listan upprepas tills listan sorteras. Eftersom Bubble sort upprepade gånger passerar genom den osorterade delen av listan, har den ett värsta fall komplexitet O (n2).

val Sortera

val Sortera är också ganska enkel men ofta överträffar bubbla Sortera., Om du väljer mellan de två, är det bäst att bara standard rätt till val Sortera. Med Urvalssortering delar vi vår inmatningslista / array i två delar: dellistan över objekt som redan sorterats och dellistan över objekt som återstår att sorteras som utgör resten av listan. Vi hittar först det minsta elementet i den osorterade underlistan och placerar den i slutet av den sorterade underlistan. Således tar vi kontinuerligt det minsta osorterade elementet och placerar det i sorterad ordning i den sorterade underlistan. Denna process fortsätter iterativt tills listan är helt sorterad.,

insättningssortering

insättningssortering är både snabbare och mycket enklare än både bubbelsortering och urvalssortering. Roligt nog, det är hur många människor sortera sina kort när man spelar ett kortspel! På varje loop iteration tar insättningssortering bort ett element från matrisen., Den hittar sedan den plats där elementet hör hemma inom en annan sorterad array och infogar den där. Det upprepar denna process tills inga inmatningselement kvarstår.

merge sort

merge sort är ett perfekt elegant exempel på en divide and conquer algoritm., Det är enkelt att använda de 2 viktigaste stegen i en sådan algoritm:

(1) Dela kontinuerligt den osorterade listan tills du har N sublister, där varje underlista har 1 element som är ”osorterat” och N är antalet element i den ursprungliga matrisen.

(2) sammanfogar upprepade gånger dvs erövrar sublisterna tillsammans 2 åt gången för att producera nya sorterade sublister tills alla element har blivit helt sammanslagna i en enda sorterad array.,

Quick Sort

Quick Sort är också en divide and conquer algoritm som merge sort. Även om det är lite mer komplicerat, utför det i de flesta standard implementeringar betydligt snabbare än sammanslagningssortering och når sällan sin värsta fallkomplexitet av O (n2)., Den har 3 huvudsteg:

(1) Vi väljer först ett element som vi kommer att ringa pivot från matrisen.

(2) Flytta alla element som är mindre än pivot till vänster om pivot; flytta alla element som är större än pivot till höger om pivot. Detta kallas partitionsoperationen.

(3) rekursivt tillämpa ovanstående 2 steg separat till var och en av under matriser av element med mindre och större värden än den sista pivot.,

Lämna ett svar

Din e-postadress kommer inte publiceras. Obligatoriska fält är märkta *