Hvordan implementeres Merge Sort i Python?



Her er en enkel og nem vejledning til at lære at bruge Merge Sort og lære om dens algoritme og implementering i Python

Denne blog er baseret på divide and conquer tilgang. Merge Sort er en 'opdele og erobre' algoritme, hvor problemet er opdelt i delproblemer og derefter flettes for at erobre løsningen. Denne blog på Merge Sort in vil gennemgå nedenstående emner i detaljer -

Hvad er Merge Sort i Python?

Flet sortering er baseret på opdelings- og erobringsalgoritmen, hvor input-arrayet er opdelt i to halvdele, derefter sorteret separat og flettes tilbage for at nå løsningen. Funktionsfletningen () bruges til at flette det sorterede .





Divide and Conquer tilgangen

  • Arrayet deles i to, og processen gentages med hver halvdel, indtil hver halvdel er af størrelse 1 eller 0.
  • Matrixen i størrelse 1 er trivielt sorteret.
  • Nu kombineres de to sorterede arrays i et stort array. Og dette fortsættes, indtil alle elementerne kombineres, og arrayet sorteres.

Her er en visualisering af flettsortering for at rydde billedet for dig

Input Array = [3,1,4,1,5,9,2,6,5,4]



Flet sort | Edureka Blogs | Edureka
Lad os nu gå videre til implementeringen.

hvad er marionet i devops

Implementering af flettsortering i Python

def mergeSort (nlist): print ('Splitting', nlist) hvis len (nlist)> 1: mid = len (nlist) // 2 venstrehalv = nlist [: mid] righthalf = nlist [mid:] mergeSort (venstre halvdel) mergeSort (højre side) i = j = k = 0, mens jeg

Produktion:

$ python main.py
('Opdeling', [3, 1, 4, 1, 5, 9, 2, 6, 5, 4])
('Opdeling', [3, 1, 4, 1, 5])
('Splitting', [3, 1])
('Splitting', [3])
('Fletning', [3])
('Splitting', [1])
('Fletning', [1])
('Fletning', [1, 3])
('Splitting', [4, 1, 5])
('Splitting', [4])
('Fletning', [4])
('Splitting', [1, 5])
('Splitting', [1])
('Fletning', [1])
('Splitting', [5])
('Fletning', [5])
('Fletning', [1, 5])
('Fletning', [1, 4, 5])
('Fletning', [1, 1, 3, 4, 5])
('Splitting', [9, 2, 6, 5, 4])
('Splitting', [9, 2])
('Splitting', [9])
('Fletning', [9])
('Splitting', [2])
('Fletning', [2])
('Fletning', [2, 9])
('Splitting', [6, 5, 4])
('Splitting', [6])
('Fletning', [6])
('Splitting', [5, 4])
('Splitting', [5])
('Fletning', [5])
('Splitting', [4])
('Fletning', [4])
('Fletning', [4, 5])
('Fletning', [4, 5, 6])
('Fletning', [2, 4, 5, 6, 9])
('Fletning', [1, 1, 2, 3, 4, 4, 5, 5, 6, 9])
[1, 1, 2, 3, 4, 4, 5, 5, 6, 9]



hvordan man bruger scannerklasse i java

Flowdiagram til implementering af Merge Sort

Fordele og anvendelse af flettsortering

De fleste af de andre algoritmer fungerer dårligt med sekventielle datastrukturer som filer og sammenkædede lister. I disse strukturer tager adgang til et tilfældigt element lineær tid, ikke regelmæssig konstant tid. Og fusionens sortering gør det let og hurtigt for sådanne datastrukturer.En af de bedste egenskaber ved fusionssortering er dens lave antal sammenligninger. Det gør O (n * log (n)) antal sammenligninger, men den konstante faktor er god sammenlignet med quicksort, hvilket gør det nyttigt, når sammenligningsfunktionen er en langsom operation.Opdel-og-erobre tilgangen til fusionssortering gør det også praktisk til parallel behandling.

Med dette kommer vi til slutningen af ​​denne blog om 'Sådan implementeres Merge Sort i Python'. Jeg håber, at indholdet tilføjede noget til din viden i Python. For at få dybtgående viden om Python sammen med dens forskellige applikationer kan du tilmelde dig live med 24/7 support og levetid adgang.