Warum sind MergeSort und BubbleSort stabil?
Hey dank Wikipedia weiß ich das Merge und BubbleSort stabil sind. Aber eine Erklärung warum das so ist wäre super
4 Antworten
Hallo!
Stabil heist in diesem Falle, dass sie bei Ausführung in keine "unstabilen" Zustände (für den Prozessor) laufen (Acess Violation) , wie z.B. Indexüberlauf, Zugriff auf nicht definierte Speicherzelle usw.
Kurz gesagt, der Computer nicht wegen dieser Algorithmen abstürzt.
Gruß
Bei BubbleSort ist das einfach einzusehen:
"In der Bubble-Phase wird die Eingabe-Liste von links nach rechts
durchlaufen. Dabei wird in jedem Schritt das aktuelle Element mit dem
rechten Nachbarn verglichen. Falls die beiden Elemente das
Sortierkriterium verletzen, werden sie getauscht."
Wenn sie das Sortierkriterium nicht verletzen, also links kleiner oder gleich wie rechts steht, werden sie nicht getauscht, d.h. bei gleich(wertig)en Elementen bleibt die ursprüngliche Reihenfolge stehen.
Auch beim Mergesort ändert sich die Reihenfolge gleichwertiger Elemente weder beim teilen noch beim mergen, geteilt wird einfach in eine linke und eine rechte Hälfte und beim merge wird beim Vergleich mit <= verglichen und somit bleibt das, was vorher links war auch weiterhin links.
Würde man bei mergesort mit < statt mit <= vergleichen, wäre der Algorithmus nicht stabil.
Stabil? Meinst du die Laufzeitkomplexität?
LG Willibergi
Stabil bedeutet bei Sortieralgorithmen, dass gleich(wertig)e Elemente stets ihre ursprüngliche Reihenfolge beibehalten und niemals durch den Algorithmus vertauscht werden. Quicksort ist ein nicht-stabiler Sortieralgorithmus.
https://de.wikipedia.org/wiki/Stabilit%C3%A4t\_%28Sortierverfahren%29
was meinst du mit stabil?