| Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung Nächste Überarbeitung | Vorherige Überarbeitung |
| faecher:informatik:oberstufe:algorithmen:sortieren:mergesort:start [26.02.2024 10:03] – [Tabelle] Marco Kuemmel | faecher:informatik:oberstufe:algorithmen:sortieren:mergesort:start [03.03.2024 10:25] (aktuell) – [Schritt für Schritt] 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}} | | | **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}} | | | 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}} | | | 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}} | | | **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}} | | | 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}} | | | 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}} | |
| | |
| | |
| | |
| | {{:aufgabe.png?nolink |}} |
| | === (A1) === |
| | |
| | Sortiere auf einem Blatt Papier mit dem MergeSort Verfahren die folgende Mistkugelreihe. |
| | |
| | {{sortieren_selection_ueb01.png?500|}} |
| | |
| | ===== Algorithmus in Pseudocode ===== |
| | Anders als bei den vorherigen Algorithmen gibt es bei Mergesort nicht mehr zwei verschachtelte Schleifen. Mergesort und Quicksort nutzen Rekursion, um das große zu sortierende Array der Reihe nach in immer kleinere (und damit einfachere) Teilarrays zu zerlegen. |
| | |
| | <code> |
| | funktion mergesort(array); |
| | falls (Länge von array <= 1) dann antworte array |
| | sonst |
| | halbiere die liste in linkesArray, rechtesArray |
| | linkesArray = mergesort(linkesArray) |
| | rechtesArray = mergesort(rechtesArray) |
| | antworte merge(linkesArray, rechtesArray) |
| | </code> |
| | Die Methode ''merge(array1, array2)'' ganz am Ende kümmert sich nur darum, die beiden bereits sortierten Teilarray wieder in korrekter Reihenfolge zu einem Array zu "verschmelzen". Dies könnte man auch direkt innerhalb der Hauptmethode implementieren, es wird nur zugunsten der Übersichtlichkeit ausgelagert. |
| | |
| | Wie bei rekursiven Vorgehensweisen üblich, umfasst der Code nur äußerst wenige Zeilen Code:\\ |
| | Die sichtbaren Zeilen in der Hauptmethode kümmern sich mit Ausnahme der letzten Zeile nur um das wiederholte Halbieren des Arrays bis nur noch eine Länge von 1 übrig bleibt (Basisfall der Rekursion). |