Nederlands
Menu

Wat is Stabiel sorteeralgoritme (stable sort)?

Sorteeralgoritme dat elementen met gelijke sleutels in hun oorspronkelijke onderlinge volgorde houdt. Bubblesort, insertion sort en mergesort zijn stabiel, terwijl selection sort, quicksort en heapsort dat in het algemeen niet zijn. Stabiliteit is nodig om achtereenvolgens op meerdere sleutels te sorteren.

Japanse benaming: 安定ソート

“Stabiel sorteeralgoritme (stable sort)” komt voor in 1 oefenvragen uit 1 onderwerpen, bijv. Datastructuren en algoritmen.

Vakgebied: Datastructuren en algoritmen

Nu oefenen: vragen over Stabiel sorteeralgoritme (stable sort)

De records (naam, score) (A, 80), (B, 70), (C, 80), (D, 70) staan in deze volgorde. In welke volgorde staan de namen als ze met een stabiel sorteeralgoritme oplopend op score worden gesorteerd?

  1. AB, D, A, C
  2. BD, B, A, C
  3. CB, D, C, A
Antwoord en toelichting tonen

Antwoord: A. B, D, A, C

Een stabiel sorteeralgoritme houdt elementen met dezelfde sleutel (hier de score) in hun oorspronkelijke onderlinge volgorde. B en D, allebei 70, blijven in de volgorde B, D, en A en C, allebei 80, in de volgorde A, C; dat geeft B, D, A, C. Bubblesort, insertion sort en mergesort zijn stabiel, terwijl selection sort, quicksort en heapsort dat in het algemeen niet zijn. Met een stabiel sorteeralgoritme kan op meerdere sleutels worden gesorteerd, bijvoorbeeld eerst op naam en daarna op score.

“Stabiel sorteeralgoritme (stable sort)” in de toelichting

Vragen met “Stabiel sorteeralgoritme (stable sort)” (1)

  1. De records (naam, score) (A, 80), (B, 70), (C, 80), (D, 70) staan in deze volgorde. In welke volgorde staan de namen als ze met een stabiel sorteeralgoritme oplopend op score worden gesorteerd?

Verwante termen

Algoritme van Dijkstra Binair zoeken (binary search) Binaire heap (binary heap) Binaire zoekboom (binary search tree) Breedte-eerst zoeken (breadth-first search) Diepte-eerst zoeken (depth-first search) Dynamisch programmeren (dynamic programming) Gelinkte lijst (linked list) Gretig algoritme (greedy algorithm) Hashtabel (hash table)

Naar de woordenlijst