Mergesort: Unterschied zwischen den Versionen

Aus KGS-Wiki
(Die Seite wurde neu angelegt: „{{subst::Quicksort}}“)
 
(Seite angelegt)
Zeile 1: Zeile 1:
[[Quicksort]] ist ein [[Algorithmus|Sortieralgorithmus]], der nach dem Prinzip ''[[Divide and Conquer]]'' arbeitet; und zwar wie folgt:
[[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, brich ab. Ansonsten…
* Wähle ein Element aus der Liste, das so genannte ''Pivot-Element''
* 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.


== 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.
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>. Anders als bei [[Quicksort]], das im schlimmsten Fall <code>n</code> Mal unterteilt werden muss, muss die Liste bei Mergesort genau <math>\log n </math> Mal unterteilt werden. Es ergibt sich eine Gesamtlaufzeit in <math>\mathcal{O}(n\log n)</math>.{{Navigationsleiste Sortieralgorithmen}}
 
=== 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 ===
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}}

Version vom 16. Januar 2024, 18:00 Uhr

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

Gegeben: Liste A der Länge n.

  • Falls n < 2: A ist sortiert, brich ab. Ansonsten…
  • Teile die Liste in zwei möglichst gleich große Hälften
  • Sortiere die beiden Hälften mit Mergesort
  • Füge die sortierten Teillisten nach folgendem Verfahren 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.

Laufzeit

Um die Liste in zwei Haufen zu unterteilen, muss man alle n Elemente betrachten, ist also in . Das Zusammenfügen am Ende hat eine Laufzeit, die nicht von der Länge der Eingabeliste abhängt, ist also in . Anders als bei Quicksort, das im schlimmsten Fall n 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=3472“