Mergesort: Unterschied zwischen den Versionen
Aus KGS-Wiki
Sn (Diskussion | Beiträge) (Seite angelegt) |
Sn (Diskussion | Beiträge) (Visualisierung eingefügt) |
||
| Zeile 1: | Zeile 1: | ||
{{Thumbnailbox|INHALT={{#mermaid:graph TD | |||
subgraph divide | |||
a[94 73 58 61 22 20 46 75] --> b[94 73 58 61] & c[22 20 46 75] | |||
b --> d[94 73] & e[58 61] | |||
c --> f[22 20] & g[46 75] | |||
d --> h[94] & i[73] | |||
e --> j[58] & k[61] | |||
f --> l[22] & m[20] | |||
g --> n[46] & o[75] | |||
end | |||
subgraph conquer | |||
h --> p[73 94] | |||
i --> p | |||
j --> q[58 61] | |||
k --> q | |||
l --> r[20 22] | |||
m --> r | |||
n --> s[46 75] | |||
o --> s | |||
p --> t[58 61 73 94] | |||
q --> t | |||
r --> u[20 22 46 75] | |||
s --> u | |||
t --> v[20 22 46 58 61 73 75 94] | |||
u --> v | |||
end}} | |||
|CAPTION=Der Mergesort-Algorithmus sortiert die Liste <code>[94, 73, 58, 61, 22, 20, 46, 75]</code>}} | |||
[[Mergesort]] 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, gib <code>A</code> zurück. | |||
# 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. | |||
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>. 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}} | 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}} | |||
Version vom 20. Januar 2024, 08:56 Uhr
Der Mergesort-Algorithmus sortiert die Liste
[94, 73, 58, 61, 22, 20, 46, 75]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:Aist sortiert, gibAzurück. - 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.
Die Schritte 1 bis 3 bilden die Divide-Phase, Schritt 4 die Conquer-Phase des Algorithmus.
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
