Denne bloggen er basert på skillet og erobre tilnærmingen. Merge Sort er en 'del og erobre' -algoritme der problemet er delt inn i delproblemer og deretter blir slått sammen for å erobre løsningen. Denne bloggen på Merge Sort in vil gå gjennom detaljene nedenfor i detalj -
- Hva er Merge Sort i Python?
- Divide and Conquer-tilnærmingen
- Implementering av Merge Sort i Python
- Flytskjema for implementering av Merge Sort
- Fordeler og bruk
Hva er Merge Sort i Python?
Merge Sort er basert på delings- og erobringsalgoritmen der inndata-arrayet er delt inn i to halvdeler, deretter sortert hver for seg og slått sammen for å nå løsningen. Funksjonen flette () brukes til å slå sammen det sorterte .
js får lengden på matrisen
Divide and Conquer-tilnærmingen
- Matrisen er delt i to og prosessen gjentas med hver halvdel til hver halvdel er av størrelse 1 eller 0.
- Matrisen av størrelse 1 er trivielt sortert.
- Nå kombineres de to sorterte matriser i ett stort utvalg. Og dette fortsetter til alle elementene er kombinert og matrisen er sortert.
Her er en visualisering av flettesortering for å fjerne bildet for deg
Input Array = [3,1,4,1,5,9,2,6,5,4]
La oss nå gå videre til implementeringen.
Implementering av Merge Sort i Python
def mergeSort (nlist): skriv ut ('Splitting', nlist) hvis len (nlist)> 1: mid = len (nlist) // 2 venstrehalv = nlist [: mid] righthalf = nlist [mid:] mergeSort (venstre halvdel) mergeSort (høyre side) i = j = k = 0 mens jeg Produksjon:
$ python main.py
(‘Splitting‘, [3, 1, 4, 1, 5, 9, 2, 6, 5, 4])
(‘Splitting‘, [3, 1, 4, 1, 5])
(‘Splitting‘, [3, 1])
(‘Splitting‘, [3])
(‘Sammenslåing‘, [3])
(‘Splitting‘, [1])
(‘Sammenslåing‘, [1])
(‘Sammenslåing‘, [1, 3])
(‘Splitting‘, [4, 1, 5])
(‘Splitting‘, [4])
(‘Sammenslåing‘, [4])
(‘Splitting‘, [1, 5])
(‘Splitting‘, [1])
(‘Sammenslåing‘, [1])
(‘Splitting‘, [5])
(‘Sammenslåing‘, [5])
(‘Sammenslåing‘, [1, 5])
(‘Sammenslåing‘, [1, 4, 5])
(‘Sammenslåing‘, [1, 1, 3, 4, 5])
(‘Splitting‘, [9, 2, 6, 5, 4])
(‘Splitting‘, [9, 2])
(‘Splitting‘, [9])
(‘Sammenslåing‘, [9])
(‘Splitting‘, [2])
(‘Sammenslåing‘, [2])
(‘Sammenslåing‘, [2, 9])
(‘Splitting‘, [6, 5, 4])
(‘Splitting‘, [6])
(‘Sammenslåing‘, [6])
(‘Splitting‘, [5, 4])
(‘Splitting‘, [5])
(‘Sammenslåing‘, [5])
(‘Splitting‘, [4])
(‘Sammenslåing‘, [4])
(‘Sammenslåing‘, [4, 5])
(‘Sammenslåing‘, [4, 5, 6])
(‘Sammenslåing‘, [2, 4, 5, 6, 9])
(‘Sammenslåing‘, [1, 1, 2, 3, 4, 4, 5, 5, 6, 9])
[1, 1, 2, 3, 4, 4, 5, 5, 6, 9]
hvordan reversere streng python
Flytskjema for implementering av Merge Sort
Fordeler og bruk av Merge Sort
De fleste av de andre algoritmene fungerer dårlig med sekvensielle datastrukturer som filer og koblede lister. I disse strukturer tar tilgang til et tilfeldig element lineær tid, ikke vanlig konstant tid. Og sammenslåingssortens art gjør det enkelt og raskt for slike datastrukturer.En av de beste egenskapene til sammenslåing er det lave antallet sammenligninger. Det gjør O (n * log (n)) antall sammenligninger, men den konstante faktoren er god sammenlignet med kviksort, noe som gjør det nyttig når sammenligningsfunksjonen er en langsom operasjon.Divide-and-conquer-tilnærmingen til fusjonssortering gjør det også praktisk for parallell behandling.
Med dette kommer vi til en slutt på denne bloggen om “Hvordan implementere Merge Sort in Python”. Jeg håper innholdet tilførte din kunnskap i Python noe. For å få grundig kunnskap om Python sammen med de forskjellige applikasjonene, kan du registrere deg for live med 24/7 support og levetidstilgang.