Nach dem wir die elementaren Sortierverfahren durch gearbeitet haben, geht es hier nun um einen etwas komplizierteren Algorithmus. Ich erkläre ihn hier kurz und bündig. Laufzeit (O-Notation), Vor-und Nachteile und seine Funktionsweise.
Inhaltsverzeichnis
Mergesort Erklärung
Der Name dieses stabilen Sortieralgorithmus bildet sich aus den englischen Wörtern „merge“ und „sort“ – also „verschmelzen“ & „sortieren“. Warum er zu den „Stabilen“ unter den Sortierverfahren gehört, erfährst du bei „Laufzeiten – O Notation“. Okay, sortieren ist ja klar. Aber warum verschmelzen? Mergesort arbeitet nach dem divide-and-conquer Prinzip (auf deutsch: teile-und-herrsche). Der Algorithmus teil also die zu sortierende Liste in mehrere kleine Liste. Und zwar so klein bis nur noch ein Element in jeder Liste steckt und fügte diese dann wieder sortiert zusammen. Daher also das „verschmelzen“. Wie das teilen funktioniert erkläre ich dir.
Vor- und Nachteile des Mergesort Algorithmus
Vorteile:
- Die Sortierung ist stabil. Das bedeutet, dass Elemente mit gleichem Wert nach der Sortierung in der gleichen Reihenfolge bleiben, in der sie vor der Sortierung waren.
- Der Algorithmus ist ein sogenannter Divide-and-Conquer Algorithmus. Das bedeutet, dass er ein Problem in kleinere Teilprobleme zerlegt und diese dann einzeln löst. Dies ist effizient, da kleinere Probleme meist leichter zu lösen sind als große.
- Der Algorithmus ist rekursiv, was bedeutet, dass er sich selbst wiederholt (rekursiert), bis das Problem gelöst ist. Dies hat den Vorteil, dass man den Code oft kürzer schreiben kann und die Lösung so elegant wie möglich ist. Nachteile des Mergesort Algorithmus
Nachteile:
- Der Algorithmus benötigt zusätzlichen Speicherplatz für die Zwischenablage (die so genannte Work Space). Dies ist notwendig, um die Elemente während der Sortierung zwischenspeichern zu können. Die Größe der Zwischenablage ist abhängig von der Größe des zu sortierenden Arrays und beträgt in der Regel O(n). Dadurch ist der Mergesort Algorithmus nicht besonders speichereffizient und eignet sich nicht für sehr große Arrays.
- Der Algorithmus ist relativ langsam, im Vergleich zu anderen Sortieralgorithmen wie dem Quicksort oder dem Heapsort. Allerdings gibt es auch Varianten des Mergesort Algorithmus, die etwas schneller sind, aber immer noch langsamer als die anderen beiden Sortieralgorithmen sind.orithmus?
Mergesort Laufzeit
Die Laufzeit des Mergesort-Algorithmus ist O(n log n), wobei n die Anzahl der Elemente im Array ist. Damit ist er effizienter als andere Sortieralgorithmen wie Selection Sort, der eine Laufzeit von O(n^) hat
Wer hat Mergesort erfunden?
Mergesort wurde 1945 von John von Neumann erfunden.
Nächste Schritte
Jetzt, wo du weißt, wie der Mergesort-Algorithmus funktioniert, kannst du versuchen, ihn selbst zu implementieren. Du kannst auch mit anderen Sortieralgorithmen experimentieren, um zu sehen, wie sie in Bezug auf Laufzeit und Effizienz abschneiden. Wenn du mehr über Sortieralgorithmen erfahren möchtest bzw. dir Code und Struktogramme reinziehen willst, dann kannst du sie dir bei Studyflix anschauen.
Du liest den Beitrag zum Mergesort Algorithmus | Erklärung der Funktionsweise
