Mergesort: Unterschied zwischen den Versionen

Aus KGS-Wiki
(Die Seite wurde neu angelegt: „{{subst::Quicksort}}“)
 
K (Beispiel aus Lua)
 
(7 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 1: Zeile 1:
[[Quicksort]] ist ein [[Algorithmus|Sortieralgorithmus]], der nach dem Prinzip ''[[Divide and Conquer]]'' arbeitet; und zwar wie folgt:
{{Thumbnailbox|INHALT={{#invoke:Mergesort|example}}
|CAPTION=Der Mergesort-Algorithmus sortiert eine Liste}}
[[Mergesort]] ist ein [[Algorithmus|Sortieralgorithmus]], der nach dem Prinzip ''[[Divide and Conquer]]'' arbeitet; und zwar wie folgt:


Gegeben: Liste <code>A</code> der Länge <code>n</code>.
Gegeben: Liste <code>A</code> der Länge <code>n</code>.


* Falls <code>n < 2</code>: <code>A</code> ist sortiert, brich ab. Ansonsten…
# Falls <code>n < 2</code>:<code>A</code> ist sortiert, gib <code>A</code> zurück.
* Wähle ein Element aus der Liste, das so genannte ''Pivot-Element''
# Ansonsten: Teile die Liste in zwei möglichst gleich große Hälften
* Teile die Liste in zwei Haufen. Auf einen Haufen kommen die Elemente, die kleiner sind als das Pivot-Element, auf den anderen Haufen die Elemente, die größer sind.
# Sortiere die beiden Hälften mit Mergesort
* Sortiere beide Haufen mit Quicksort; du erhältst zwei sortierte Listen
# Füge die sortierten Teillisten nach folgendem Verfahren zusammen:
* Füge die beiden sortierten Teillisten mit dem Pivot-Element zu einer sortierten Gesamtliste zusammen.
## Betrachte das erste Element der beiden Teillisten
## Wähle das kleinere davon aus, entferne es aus der Teilliste und füge es in die sortierte Gesamtliste ein
## Wiederhole diese beiden Schritte für den Rest der beiden Teillisten, bis beide leer sind.
 
Die Schritte 1 bis 3 bilden die ''Divide''-Phase, Schritt 4 die ''Conquer''-Phase des Algorithmus.


== Laufzeit ==
== Laufzeit ==
Um die Liste in zwei Haufen zu unterteilen, muss man alle <code>n</code> Elemente betrachten, ist also in <math>\mathcal{O}(n)</math>. Das Zusammenfügen am Ende hat eine Laufzeit, die nicht von der Länge der Eingabeliste abhängt, ist also in <math>\mathcal{O}(1)</math>. Die Frage ist nun, wie oft die Liste unterteilt werden muss.
In der ''Divide''-Phase werden überhaupt keine Zahlen betrachtet und keine Vergleiche angestellt. Das geschieht erst in der ''Conquer''-Phase. Hier wird die gesamte Liste mehrmals durchlaufen, während die einzelnen Elemente zu sortierten Paaren ge-merge-t werden, die Paare zu Quartetten und so weiter. Jeder dieser Sortierschritte läuft in {{O|n}} und die Anzahl der Durchgänge lässt sich mit <math>\log(n)</math> abschätzen. Anders als bei [[Quicksort]], das im schlimmsten Fall <math>n</math> Mal unterteilt werden muss, muss die Liste bei Mergesort genau <math>\log n</math> Mal unterteilt werden. Es ergibt sich eine [[Laufzeit|Gesamtlaufzeit]] in {{O|n\log n}}.
 
=== Worst Case ===
Im schlechtesten Fall wählt man das Pivot-Element so ungeschickt, dass der gesamte Rest der Liste immer auf einem Haufen landet. Dies ist der Fall, wenn man als Pivot-Element das größte oder das kleinste Element der Liste wählt. In diesem Fall muss die Liste <code>n-1</code> Mal in Haufen unterteilt werden, es ergibt sich eine Laufzeit in <math>\mathcal{O}(n^2)</math>.


=== Best Case ===
{{Navigationsleiste Sortieralgorithmen|LINKS=* [https://www.youtube.com/watch?v=dENca26N6V4 Mergesort getanzt] {{Flagge|GB}}}}
Im besten Fall wählt man das Pivot-Element so geschickt, dass man die Liste immer in zwei exakt gleich große Haufen teilt. Dann muss die Liste etwa <math>\log n</math> Mal in Haufen unterteilt werden; es ergibt sich eine Laufzeit in <math>\mathcal{O}(n\log n)</math>.{{Navigationsleiste Sortieralgorithmen}}

Aktuelle Version vom 3. Juni 2024, 14:20 Uhr

graph TD subgraph divide a[76 70 15 97 29 29 65 50] a --> b[76 70 15 97] & c[29 29 65 50] b --> d[76 70] & e[15 97] c --> f[29 29] & g[65 50] d --> h[76] & i[70] e --> j[15] & k[97] f --> l[29] & m[29] g --> n[65] & o[50] end subgraph conquer h --> p[70 76] i --> p j --> q[15 97] k --> q l --> r[29 29] m --> r n --> s[50 65] o --> s p --> t[15 70 76 97] q --> t r --> u[29 29 50 65] s --> u t --> v[15 29 29 50 65 70 76 97] u --> v end

Der Mergesort-Algorithmus sortiert eine Liste

Mergesort ist ein Sortieralgorithmus, der nach dem Prinzip Divide and Conquer arbeitet; und zwar wie folgt:

Gegeben: Liste A der Länge n.

  1. Falls n < 2:A ist sortiert, gib A zurück.
  2. Ansonsten: Teile die Liste in zwei möglichst gleich große Hälften
  3. Sortiere die beiden Hälften mit Mergesort
  4. Füge die sortierten Teillisten nach folgendem Verfahren zusammen:
    1. Betrachte das erste Element der beiden Teillisten
    2. Wähle das kleinere davon aus, entferne es aus der Teilliste und füge es in die sortierte Gesamtliste ein
    3. Wiederhole diese beiden Schritte für den Rest der beiden Teillisten, bis beide leer sind.

Die Schritte 1 bis 3 bilden die Divide-Phase, Schritt 4 die Conquer-Phase des Algorithmus.

Laufzeit

In der Divide-Phase werden überhaupt keine Zahlen betrachtet und keine Vergleiche angestellt. Das geschieht erst in der Conquer-Phase. Hier wird die gesamte Liste mehrmals durchlaufen, während die einzelnen Elemente zu sortierten Paaren ge-merge-t werden, die Paare zu Quartetten und so weiter. Jeder dieser Sortierschritte läuft in und die Anzahl der Durchgänge lässt sich mit abschätzen. Anders als bei Quicksort, das im schlimmsten Fall Mal unterteilt werden muss, muss die Liste bei Mergesort genau Mal unterteilt werden. Es ergibt sich eine Gesamtlaufzeit in .


Weblinks

Abgerufen von „https://wiki.kah.gs/index.php?title=Mergesort&oldid=5247“