Slå sammen sorteringsalgoritme ved hjelp av Python

I denne artikkelen skal vi lære om en merge -algoritme. Merge-sort er en populær skill-og-er-sorteringsmetode. Merge -sort brukes mye på grunn av hastigheten i sortering av data. Det er en av de bedre illustrasjonene av hvordan du kan dele og erobre algoritmer som kan brukes i praksis. Merge -sort skiller en liste over data i to halvdeler og kaller deretter disse underdelene for å dele dem videre i to halvdeler. Den gjentar operasjonen til hver listekomponent bare har ett element. Ved å sortere disse underdelene med ett element i to komponenter, vil det senere slå dem sammen. Etter sortering vil to-element-delen være koblet til de to andre komponentene. Denne prosedyren gjentas til den endelige sorterte listen over elementer er oppnådd ved å påkalle funksjonen gjentatte ganger.

Den grunnleggende illustrasjonen av Merge -sorteringen er gitt i følgende eksempel:

Python -kode: Følgende Python -kode er for Merge Sort -algoritmen:

Def Merge_Sort (UNSORTEDLIST):
Hvis len (usortert liste)> 1:
midt = len (usortert liste) // 2
Venstrelist = UNSORTEDLIST [: MID]
Rettsliste = UsortertList [Midt:]
# Rekursiv samtale når vi går to liste (venstre og høyre) for sortering
Merge_sort (venstreliste)
Merge_sort (høyreliste)
# Fordi vi har to lister, så vi må iteratorer for iterasjon av hver liste
m = 0
n = 0
# Vi trenger en vanlig iterator som itererer til hovedlisten
z = 0
mens m < len(leftList) and n < len(rightList):
Hvis venstreseliste [M] <= rightList[n]:
# Her bruker vi de første venstre sideelementene
UsortertList [z] = venstreliste [M]
# Øk den viktigste iteratoren
M += 1
ellers:
UsortertList [z] = Rettliste [n]
n += 1
z += 1
# Hvis verdier er igjen på listen, behandler vi her
mens m < len(leftList):
UsortertList [z] = venstreliste [M]
M += 1
z += 1
mens n < len(rightList):
UsortertList [z] = Rettliste [n]
n += 1
z += 1
UNSORTEDLIST = [23,56,0,23,85,100,200,12,32,78,90,102]
Merge_sort (UNSORTEDLIST)
trykte (usortert liste)

Produksjon:

[0, 12, 23, 23, 32, 56, 78, 85, 90, 100, 102, 200]

Dette er den rekursive måten å slå sammen sort implementering på. Her er følgende trinn for å få den sorterte matrisen ved å bruke denne metoden:

• Linje 1: Vi definerer en funksjon (Merge_sort) når vi trenger å sortere en liste over usorterte elementer. Nå skal vi forklare alle linjer i denne Merge_Sort -funksjonen.
• Linje 2-5: Det første vi sjekker er om de usorterte listeelementene har mer enn 1 element eller ikke. Hvis det bare er et enkelt element, er det ikke nødvendig å sortere. Så vi sjekker denne første tilstanden.

  Hvis elementene er mer enn 1, prøver vi å få medianverdien på listen til å dele hele listen i to deler (venstre og høyre) for ytterligere rekursiv samtale. Hver rekursive samtale deler listen inn i venstre og høyre til to tilstøtende oppføringer er anskaffet.

• Linje 8-9: Vi kaller Merge Sort rekursivt for hver sublist (venstre og høyre).
• Linje 11-15: Sorteringsprosedyren starter nå. Hver ringer to deler som er krysset av M og N -iteratorene. Z iterator itererer på tvers av alle listene, og gjør endringer når det går.
• Linje 17-26: Venstrelist [m] er tildelt den usorterte [z] -sporet, og m økes hvis verdien til m er mindre enn verdien ved n. Hvis ikke, er høyliste [n] valgt. Alle verdier tildelt Z er alle sortert.
• Linje 29-37: På slutten av denne sløyfen kan det hende at en av delene ikke har blitt krysset fullstendig. Innholdet er tildelt de gjenværende stillingene på listen.

Tidskompleksitet:

Tidskompleksiteten til flettesorteringen avhenger av to faktorer:

• Listen delte faktor som tar logg (n)
• Den andre faktoren smelter sammen den to listen, som tar lineær tid, så dens kompleksitet er O (n)

Dermed er den totale kompleksiteten basert på de to foregående faktorene av Merge -sorteringen er o (n.logg).

Fordeler med Merge Sort -algoritmen:

• Fusjonssortering gjør det enkelt å sortere big datasett.
• Merge -sort kan få tilgang til data i rekkefølge, og det er derfor ikke nødvendig med tilfeldig tilgang.
• Merge -sort er en pålitelig sorteringsmetode.

Ulemper med Merge Sort -algoritmen:

• Merge -sorteringen krever en lignende størrelse for å sortere listen, noe som er en ulempe med minnebruken.
• Når du sorterer mindre datasett, tar det lengre tid.

Konklusjon:

Fusjonssortering er en rask og allsidig sorteringsmetode. Den viktigste fordelen er algoritmens konsistente kjøretid og effektivitet mens du sorterer store matriser. Sammenlignet med rask sortering, er det ikke avhengig av noen defekte vurderinger som resulterer i lange driftstider. Merge -sorteringen er den beste algoritmen for å sortere elementene. Imidlertid er den viktigste ulempen med Merge -sorteringen at den bruker mye minne før du slår sammen elementene. Det er også veldig nyttig for fremtidig programvareteknikk, der de kan bygge flere sorteringsalgoritmer basert på Divide-and-Conquer-metoden.

Vi så standardeksemplet på Merge Sort uten å kode først for å forstå hvordan denne analogien fungerer, og deretter implementerte vi lignende trinn i Python -programmering. Nå er vi klar over skillet og erobrer teknologien til Merge Sort. Vi håper du fant denne artikkelen nyttig. Sjekk ut Linux -hint for flere tips og informasjon.