Mergesort: Unterschied zwischen den Versionen

Aus KGS-Wiki
Zum nächsten Versionsunterschied →
VisuellWikitext
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 𝒪(n). Das Zusammenfügen am Ende hat eine Laufzeit, die nicht von der Länge der Eingabeliste abhängt, ist also in 𝒪(1). Anders als bei Quicksort, das im schlimmsten Fall n Mal unterteilt werden muss, muss die Liste bei Mergesort genau log⁡n Mal unterteilt werden. Es ergibt sich eine Gesamtlaufzeit in 𝒪(nlog⁡n).

Weblinks


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