Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
| Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung Nächste Überarbeitung | Vorherige Überarbeitung Nächste ÜberarbeitungBeide Seiten, nächste Überarbeitung |
| faecher:informatik:oberstufe:algorithmen:sortieren:mergesort:start [23.02.2024 12:54] – [Mergesort] Marco Kuemmel | faecher:informatik:oberstufe:algorithmen:sortieren:mergesort:start [26.02.2024 11:03] – [Tabelle] Marco Kuemmel |
|---|
| |
| ====== Schritt für Schritt ====== | ====== Schritt für Schritt ====== |
| | | **Split-Phase**: Das Array ist noch zu lang. Es wird mehrfach an der (abgerundeten) Hälfte halbiert, bis jedes Teilarray nur noch die Länge 1 hat. | {{ :faecher:informatik:oberstufe:algorithmen:sortieren:mergesort:merge01.png?600}} | |
| | | Jedes Teilarray muss nochmal gesplittet werden... | {{ :faecher:informatik:oberstufe:algorithmen:sortieren:mergesort:merge02.png?600}} | |
| | | Das hinterste Teilarray hat noch immer die Länge 2. Daher muss es nochmals halbiert werden. \\ Damit ist das Ende der Split-Phase erreicht. | {{ :faecher:informatik:oberstufe:algorithmen:sortieren:mergesort:merge03.png?600}} | |
| | | **Merge-Phase** (Verschmelzungsphase): Wir wissen nun, dass alle Teilarrays der Länge 1 jeweils offensichtlich sortiert sind. \\ Nun fügen wir jeweils benachbarte Teilarrays in der korrekten Reihenfolge wieder zusammen. \\ Dabei sollte die Reihenfolge beachtet werden, in der die Arrays zuvor aufgesplittet wurden. | {{ :faecher:informatik:oberstufe:algorithmen:sortieren:mergesort:merge04.png?600}} | |
| | | Die beiden äußeren Teilarrays werden nun korrekt zusammengefügt. | {{ :faecher:informatik:oberstufe:algorithmen:sortieren:mergesort:merge05.png?600}} | |
| | | Als letzter Merge-Schritt müssen nur noch die beiden letzten Teilarrays zusammengefügt werden. \\ Hier ist gut sichtbar: man muss immer nur die beiden verbleibenden vordersten (=kleinsten) Zahlen der beiden Teilarrays miteinander vergleichen, \\ um festzustellen, welche Zahl als nächste ausgewählt wird.\\ __Kleinschrittig: __\\ - Vergleiche die vordere 3 mit der vorderen 1. Wähle und entferne die 1, da diese kleiner ist. \\ - Vergleiche die vordere 3 mit der vorderen 2. Wähle und entferne die 2, da diese kleiner ist.\\ - Vergleiche die vordere 3 mit der vorderen 5. Wähle und entferne die 3, da diese kleiner ist.\\ - Vergleiche die vordere 4 mit der vorderen 5. Wähle und entferne die 4, da diese kleiner ist.\\ - Es bleibt nur noch die rechte 5 übrig. Wähle und entferne die 5. | {{ :faecher:informatik:oberstufe:algorithmen:sortieren:mergesort:merge06.png?600}} | |