Warum sind MergeSort und BubbleSort stabil?

... komplette Frage anzeigen

4 Antworten

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 bewerten Vielen Dank für Deine Bewertung

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 bewerten Vielen Dank für Deine Bewertung

Stabil? Meinst du die Laufzeitkomplexität?

LG Willibergi

Antwort bewerten Vielen Dank für Deine Bewertung

was meinst du mit stabil?

Antwort bewerten Vielen Dank für Deine Bewertung

Was möchtest Du wissen?