wie funktioniert merge sort?
3 Antworten
Der Kern beim Mergesort sind die Mergephasen, also das Zusammenführen. Eien solche MErgephase nimmt zwei (bereits sortierte) Listen und führt sie sortiert zusammen, indem sie die vordersten Elemente vergleich und das kleinere nimmt, bis beide Listen leer sind. Aus zwei sortierten Listen der Länge l entsteht eien sortierte Liste der Länge 2l.
Wennich nun hingehe und mit 1-elementigen Listen anfange, dann konstruiere ich sortiere 2-elementige Listen. In der nächsten Mergephase megre ich immer 2 Listen a 2 Elemente zu Listen mit 4-Elementen.
Der PRozess wird wiederholt, bis nur noch 1 sortierte Liste vorliegt.
5 8 9
1 3 7
----------------------------------
1<5, ja, 1
3<5, ja, 3
7<5, nein, 5
7<8, ja, 7 (Liste 2 leer, Liste 1 anhängen)
Ergebnis
1,3,5,7,8,9
Es werden immer die vorderen beiden Elemente verglichen, das kleinere in die neue Liste gepackt.
Technisch kannst du statt entfernen natürlich auch einfach den Index weiterschieben - das sind dann nur Implementierungsdetails.
Du teilst deine Elemente sowiet auf, bis du nru noch zwei Elemente hast und bringts diese in die richtige Reihenfolge.
Dann mergst du jeweils zwei Listen zu einer größeren zusammen, indem du jeweils die Elemente an einem Ende der Listen vergleichst und zusammenspliect.
4 2 3 1
=>
4 2 | 3 1
=>
2 4 | 1 3
Dann splicen/mergen:
2 4
1 3
=>
2 4
1 | 3
=>
4
1 2 | 3
=>
4
1 2 3 |
=>
1 2 3 4 |
Mergesort betrachtet die zu sortierenden Daten als Liste und zerlegt sie in kleinere Listen, die jede für sich sortiert werden. Die kleinen sortierten Listen werden dann im Reißverschlussverfahren zu größeren sortierten Listen zusammengefügt (engl. (to) merge), bis eine sortierte Gesamtliste erreicht ist
Siehe z.b. hier
Kannst du kurz erklären wie die merger Phasen funktionieren, also ich habe meinetwegen 2 3 und 5 8 und die will ich zusammenführen, wie genau wird das gemacht ? einfach alles durchgehen und vergleichen also wenn 2 kleiner 5 füge an Stelle des temporären arrays ein , wenn 3 kleiner 5 füge ein und dann 5 und 8 einfach so ?