Deutsch
Menü

Was ist Stabiles Sortierverfahren (Stable Sort)?

Sortierverfahren, das Elemente mit gleichem Schlüssel in ihrer ursprünglichen Reihenfolge belässt. Bubblesort, Insertionsort und Mergesort sind stabil, Selectionsort, Quicksort und Heapsort im Allgemeinen nicht. Stabilität ist nötig, wenn nacheinander nach mehreren Schlüsseln sortiert wird.

Japanische Bezeichnung: 安定ソート

„Stabiles Sortierverfahren (Stable Sort)“ kommt in 1 Übungsfragen aus 1 Themen vor, z. B. Datenstrukturen und Algorithmen.

Fachgebiet: Datenstrukturen und Algorithmen

Jetzt üben: Fragen zu Stabiles Sortierverfahren (Stable Sort)

Die Datensätze (Name, Punktzahl) (A, 80), (B, 70), (C, 80), (D, 70) liegen in dieser Reihenfolge vor. In welcher Reihenfolge erscheinen die Namen, wenn mit einem stabilen Sortierverfahren aufsteigend nach Punktzahl sortiert wird?

  1. AB, D, A, C
  2. BD, B, A, C
  3. CB, D, C, A
Antwort und Erläuterung anzeigen

Antwort: A. B, D, A, C

Ein stabiles Sortierverfahren behält die ursprüngliche Reihenfolge von Elementen mit gleichem Schlüssel (hier der Punktzahl) bei. B und D, beide mit 70, bleiben in der Reihenfolge B, D, und A und C, beide mit 80, in der Reihenfolge A, C; es ergibt sich B, D, A, C. Bubblesort, Insertionsort und Mergesort sind stabil, Selectionsort, Quicksort und Heapsort im Allgemeinen nicht. Mit einem stabilen Verfahren lässt sich nach mehreren Schlüsseln sortieren, etwa zuerst nach Namen und dann nach Punktzahl.

„Stabiles Sortierverfahren (Stable Sort)“ in den Erläuterungen

Fragen mit „Stabiles Sortierverfahren (Stable Sort)“ (1)

  1. Die Datensätze (Name, Punktzahl) (A, 80), (B, 70), (C, 80), (D, 70) liegen in dieser Reihenfolge vor. In welcher Reihenfolge erscheinen die Namen, wenn mit einem stabilen Sortierverfahren aufsteigend nach Punktzahl sortiert wird?

Verwandte Begriffe

Binäre Suche (Binary Search) Binärer Heap (Binary Heap) Binärer Suchbaum (Binary Search Tree) Breitensuche (Breadth-First Search) Dijkstra-Algorithmus Dynamische Programmierung Greedy-Algorithmus Hashtabelle (Hash Table) Rekursion Stack (Stapelspeicher)

Zur Glossarübersicht