Frage von DarkVamp93, 73

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

Antwort
von Schachpapa, 29

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.

Antwort
von Tschoo, 25

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ß

Antwort
von Willibergi, 34

Stabil? Meinst du die Laufzeitkomplexität?

LG Willibergi

Kommentar von Schachpapa ,

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

Antwort
von VBHHerzog, 32

was meinst du mit stabil?

Keine passende Antwort gefunden?

Fragen Sie die Community