Stabiler Sortieralgorithmus
-
Hallo zusammen,
leider verstehe ich die wikipedia Erklärung für einen stabilen/instabilen Sortieralgorithmus nicht. Kann mir jemand den Unterschied erklären. Ich vermute, dass ein stabiler Algorithmus schon sortierte Elemente nicht anrührt und instabile, wie MergeSort, diese trotzdem erstmal bearbeitet. Liege ich richtig?Vielen Dank
lg, freakC++
-
Ein stabiler Sortieralgorithmus ändert die Reihenfolge von gleichen Elementen nicht.
-
Also liege ich richtig?
lg, freakC++
-
freakC++ schrieb:
Also liege ich richtig?
Nein, das hat mit "schon sortiert" nichts zu tun.
Es geht nur um solche Elemente, die im Sinne des Sortierkritieriums gleich sind. Deren Reihenfolge relativ zueinander wird nicht verändert.
Angenommen, du sortierst ein int-Array, und da sind drei Elemente mit dem Wert 4 drin. Nach dem Sortieren stehen die natürlich direkt hintereinander. Aber nur bei einem stabilen Sortieralgorithmus kannst du dich darauf verlassen, dass die Elemente immer noch dieselbe Reihenfolge unterander haben.
Solange du nur ints sortierst, ist das natürlich mehr oder weniger witzlos, weil du eine 4 nicht von der anderen unterscheiden kannst. Interessant wird das erst, wenn die Elemente noch andere Daten haben außer dem, nach dem sortiert wird.
-
Ok, danke schön! Habs verstanden!
Bis bald
lg, freakC++