Mergesort: Unterschied zwischen den Versionen

Keine Bearbeitungszusammenfassung
K 1 Version importiert
 
(3 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 1: Zeile 1:
== Einführung ==
== Einführung ==
{{#ev:youtube|KuNLzdRnwTU|320|poster=Datei:Vorschau YouTube KuNLzdRnwTU.jpg|title=Mergesort Schritt für Schritt – mit Java-Code}}
Ein in der Praxis häufig eingesetzter, sehr effizienter und im Gegensatz zu [[Quicksort]] auch [[Sortieren#Stabilität|stabiler]] [[Sortieren|Sortieralgorithmus]] ist der '''Mergesort''' (Sortieren durch Mischen). Er funktioniert nach dem Prinzip '''„Teile und herrsche“''' (''Divide and Conquer''), bei dem aus einem großen Problem zwei kleinere Teilprobleme gemacht werden, was in der Programmierung mithilfe von [[Rekursion]] umgesetzt wird.
Ein in der Praxis häufig eingesetzter, sehr effizienter und im Gegensatz zu [[Quicksort]] auch [[Sortieren#Stabilität|stabiler]] [[Sortieren|Sortieralgorithmus]] ist der '''Mergesort''' (Sortieren durch Mischen). Er funktioniert nach dem Prinzip '''„Teile und herrsche“''' (''Divide and Conquer''), bei dem aus einem großen Problem zwei kleinere Teilprobleme gemacht werden, was in der Programmierung mithilfe von [[Rekursion]] umgesetzt wird.


Zeile 16: Zeile 18:
# Es werden immer nur die beiden vordersten Zahlen <code>feld[i]</code> und <code>feld[j]</code> miteinander verglichen.
# Es werden immer nur die beiden vordersten Zahlen <code>feld[i]</code> und <code>feld[j]</code> miteinander verglichen.
# Ist <code>feld[i] <= feld[j]</code>, wird die Zahl aus der linken Hälfte in <code>hilf[k]</code> eingetragen und <code>i</code> rückt um 1 weiter. Andernfalls wird die Zahl aus der rechten Hälfte in <code>hilf[k]</code> übernommen und <code>j</code> rückt weiter. In beiden Fällen rückt <code>k</code> auf die nächste freie Stelle. (Durch das <code><=</code> wird bei gleichen Zahlen stets die linke Zahl zuerst übernommen – dadurch bleibt die Reihenfolge gleicher Elemente erhalten und Mergesort ist [[Sortieren#Stabilität|stabil]]).
# Ist <code>feld[i] <= feld[j]</code>, wird die Zahl aus der linken Hälfte in <code>hilf[k]</code> eingetragen und <code>i</code> rückt um 1 weiter. Andernfalls wird die Zahl aus der rechten Hälfte in <code>hilf[k]</code> übernommen und <code>j</code> rückt weiter. In beiden Fällen rückt <code>k</code> auf die nächste freie Stelle. (Durch das <code><=</code> wird bei gleichen Zahlen stets die linke Zahl zuerst übernommen – dadurch bleibt die Reihenfolge gleicher Elemente erhalten und Mergesort ist [[Sortieren#Stabilität|stabil]]).
# Sobald eine der beiden Hälften vollständig verbraucht ist, wird der '''Rest''' der anderen Hälfte '''ohne weitere Vergleiche''' hinten an das Hilfsfeld angehängt, da diese Zahlen bereits sortiert und größer als alle bisherigen Zahlen sind.
# Sobald eine der beiden Hälften vollständig verbraucht ist, wird der '''Rest''' der anderen Hälfte '''ohne weitere Vergleiche''' hinten an das Hilfsfeld angehängt, da diese Zahlen bereits sortiert und mindestens so groß wie alle bisherigen Zahlen sind.
# Zum Schluss wird der Inhalt von <code>hilf</code> zurück in das ursprüngliche <code>feld</code> kopiert.
# Zum Schluss wird der Inhalt von <code>hilf</code> zurück in das ursprüngliche <code>feld</code> kopiert.


Zeile 85: Zeile 87:


=== Schreibtischtest (Reihenfolge der Aufrufe) ===
=== Schreibtischtest (Reihenfolge der Aufrufe) ===
Bei einem Schreibtischtest im Abitur muss die Feldbelegung nach jedem Aufruf von <code>mische</code> angegeben werden. Wichtig: Java arbeitet den Rekursionsbaum '''nicht Ebene für Ebene''' ab, sondern steigt durch den ersten rekursiven Aufruf <code>mergeSort(feld, links, mitte)</code> zuerst in der linken Hälfte komplett in die Tiefe ab, bevor die rechte Hälfte betrachtet wird:
Bei einem Schreibtischtest im Abitur wird üblicherweise die Feldbelegung nach jedem Aufruf von <code>mische</code> angegeben. Wichtig: Java arbeitet den Rekursionsbaum '''nicht Ebene für Ebene''' ab, sondern steigt durch den ersten rekursiven Aufruf <code>mergeSort(feld, links, mitte)</code> zuerst in der linken Hälfte komplett in die Tiefe ab, bevor die rechte Hälfte betrachtet wird:


{| class="wikitable"
{| class="wikitable"
Zeile 111: Zeile 113:
Während auf einem [[Array]] oft [[Quicksort]] bevorzugt wird, weil Mergesort dort ein zusätzliches Hilfsfeld <code>hilf</code> benötigt, ist '''Mergesort das optimale Sortierverfahren für verkettete Listen''' – insbesondere schon für '''einfach verkettete Listen''', deren Knoten lediglich eine Referenz <code>naechster</code> auf den Nachfolger, aber keinen Verweis <code>vorgaenger</code> besitzen:
Während auf einem [[Array]] oft [[Quicksort]] bevorzugt wird, weil Mergesort dort ein zusätzliches Hilfsfeld <code>hilf</code> benötigt, ist '''Mergesort das optimale Sortierverfahren für verkettete Listen''' – insbesondere schon für '''einfach verkettete Listen''', deren Knoten lediglich eine Referenz <code>naechster</code> auf den Nachfolger, aber keinen Verweis <code>vorgaenger</code> besitzen:


* '''Warum [[Quicksort]] und Insertion Sort eine zweifach verkettete Liste benötigen:'''
* '''Warum [[Quicksort]] und Insertion Sort in den hier betrachteten Implementierungen einen Vorgängerzeiger nutzen (zweifach verkettete Liste):'''
** Bei '''[[Quicksort]]''' wird für den rekursiven Aufruf der linken Teilliste der Knoten unmittelbar ''vor'' dem Pivot-Knoten als neue rechte Grenze benötigt. Nur in einer bidirektionalen (zweifach verketteten) Liste mit <code>vorgaenger</code>-Zeiger und <code>endeKnoten</code> ist dieser Zugriff über <code>pivotKnoten.getVorgaenger()</code> direkt in <math>\mathcal{O}(1)</math> möglich. Auf einer einfach verketteten Liste müsste man den Vorgänger jedes Mal vom <code>startKnoten</code> aus in <math>\mathcal{O}(n)</math> suchen.
** Bei '''[[Quicksort]]''' wird für den rekursiven Aufruf der linken Teilliste der Knoten unmittelbar ''vor'' dem Pivot-Knoten als neue rechte Grenze benötigt. Nur in einer bidirektionalen (zweifach verketteten) Liste mit <code>vorgaenger</code>-Zeiger und <code>endeKnoten</code> ist dieser Zugriff über <code>pivotKnoten.getVorgaenger()</code> direkt in <math>\mathcal{O}(1)</math> möglich. Auf einer einfach verketteten Liste müsste man den Vorgänger jedes Mal vom <code>startKnoten</code> aus in <math>\mathcal{O}(n)</math> suchen.
** Auch '''Insertion Sort''' profitiert stark von einer Doppelverkettung, da der Suchzeiger über <code>getVorgaenger()</code> direkt vom aktuellen Element aus rückwärts durch den sortierten Bereich wandern kann, statt jedes Mal beim <code>startKnoten</code> neu zu beginnen.
** Auch '''Insertion Sort''' profitiert stark von einer Doppelverkettung, da der Suchzeiger über <code>getVorgaenger()</code> direkt vom aktuellen Element aus rückwärts durch den sortierten Bereich wandern kann, statt jedes Mal beim <code>startKnoten</code> neu zu beginnen.
** Dabei bezeichnet <code>startKnoten</code> den ersten und <code>endeKnoten</code> den letzten Knoten der betrachteten Teilliste, <code>pivotKnoten</code> den Pivot-Knoten. <code>getVorgaenger()</code> liefert den Vorgängerknoten, <code>getNaechster()</code> und <code>setNaechster(...)</code> lesen und setzen den Nachfolger eines Knotens.
* '''Warum Mergesort bereits auf einer einfach verketteten Liste ideal arbeitet:'''
* '''Warum Mergesort bereits auf einer einfach verketteten Liste ideal arbeitet:'''
*# '''Reine Vorwärtsnavigation über <code>naechster</code>:''' Beim Mischen zweier sortierter Teillisten werden immer nur die vordersten Knoten verglichen und über <code>getNaechster()</code> in Vorwärtsrichtung weitergeschaltet. Ein <code>vorgaenger</code>-Zeiger bringt für Mergesort keinen Vorteil, weil niemals rückwärts navigiert werden muss. Auch die Listenmitte lässt sich vorwärts bestimmen (ein langsamer Zeiger rückt einen Knoten weiter, ein schneller Zeiger zwei Knoten).
*# '''Reine Vorwärtsnavigation über <code>naechster</code>:''' Beim Mischen zweier sortierter Teillisten werden immer nur die vordersten Knoten verglichen und über <code>getNaechster()</code> in Vorwärtsrichtung weitergeschaltet. Ein <code>vorgaenger</code>-Zeiger bringt für Mergesort keinen Vorteil, weil niemals rückwärts navigiert werden muss. Auch die Listenmitte lässt sich vorwärts bestimmen (ein langsamer Zeiger rückt einen Knoten weiter, ein schneller Zeiger zwei Knoten).
Zeile 120: Zeile 123:
== Laufzeitanalyse ==
== Laufzeitanalyse ==
Für die [[Laufzeitanalyse]] betrachten wir die Anzahl der Teilungsebenen und die Anzahl der Vergleiche pro Ebene:
Für die [[Laufzeitanalyse]] betrachten wir die Anzahl der Teilungsebenen und die Anzahl der Vergleiche pro Ebene:
* '''Anzahl der Ebenen:''' Da das Feld in jedem Schritt halbiert wird (<math>8 \rightarrow 4 \rightarrow 2 \rightarrow 1</math>), lässt sich ein Feld mit <math>n</math> Zahlen genau <math>\log_2(n)</math>-mal teilen (bei <math>n = 8</math> sind es <math>\log_2(8) = 3</math> Ebenen).
* '''Anzahl der Ebenen:''' Da das Feld in jedem Schritt halbiert wird (<math>8 \rightarrow 4 \rightarrow 2 \rightarrow 1</math>), lässt sich ein Feld mit <math>n</math> Zahlen höchstens <math>\lceil \log_2(n) \rceil</math>-mal teilen (bei <math>n = 8</math> genau <math>\log_2(8) = 3</math>-mal, also in 3 Ebenen).
* '''Vergleiche pro Ebene:''' Auf jeder Ebene wird mit jedem Vergleich genau eine Zahl in das Hilfsfeld übertragen. Für <math>n</math> Zahlen sind pro Ebene also '''höchstens <math>n</math> Vergleiche''' nötig.
* '''Vergleiche pro Ebene:''' Auf jeder Ebene wird mit jedem Vergleich genau eine Zahl in das Hilfsfeld übertragen. Für <math>n</math> Zahlen sind pro Ebene also '''höchstens <math>n</math> Vergleiche''' nötig.


Zeile 146: Zeile 149:


[[Kategorie:Programmierung]]
[[Kategorie:Programmierung]]
[[Kategorie:AHR_I_Informatik_LK]]
[[Kategorie:FI_I_TP2]]