Warum sind MergeSort und BubbleSort stabil?

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.

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ß

Stabil? Meinst du die Laufzeitkomplexität?

LG Willibergi

Warum ist nur Iod (127) stabil?

...zur Frage

Bionik - Warum ist Holz stabiles Tragwerk?

Hallo, eine Frage zur Bionik: Warum eignet sich Holz besonders beim Bau von Häusern und vor allem: Warum ist es so stabil?

Grüße, Kou

...zur Frage

Warum braucht man beim Diesel eine glühkerze?

Der Dieselmotor entzündet sich durch Luft Komprimierung selbst . Warum wird dann bzw wann Diesel eingespritzt ? Und warum braucht man dann ne glühkerze , wenn durch die Verdichtung eine Selbstentzündung stattfindet ? Wie hängt das mit dem Start zusammen - vorglühen ??? Eine tolle Erklärung wäre super , vielen Dank :)

...zur Frage

Warum landet man bei Wikipedia immer früher oder später bei Philosphie?

Hey,

Wenn man in Wikipedia irgendeinen Artikel auswählt und ab da immer den ersten Wissensartikel anklickt (also keine Sprach/Begriffserklärungen), dann landet man immer bei Philosophie. Zumindest im Englischen Wikipedia, beim Deutschen funtionierts aber auch bei fast allen Seiten.

Das kann doch kein Zufall sein, oder? Aber warum ist das so?

Grüße :)

...zur Frage

Warum wurde dei Weimarer Republik Judenrepublik genannt?

Hey

wenn mir jemand diese Frage VERSTÄNDLICH erklären könnte wäre das echt super... hab nichts dazu gefunden aber im Geschichtsbuch steht es (ohne erklärung -.-) und ich brauche die Antwort für meine Geschichtsprüfung!!! wäre toll =) danke =)

...zur Frage

Physik Frisbee

Eine Frisbee-Scheibe muss sich schnell drehen, damit sie stabil und weit fliegt. Was wäre die Erklärung dafür?

...zur Frage

Was möchtest Du wissen?