Źródło: Arkusze CKE
Wskaż algorytm sortowania, który nie jest stabilny?
Warianty odpowiedzi
-
A
sortowanie przez zliczanie
-
B
sortowanie bąbelkowe
-
C
sortowanie szybkie
-
D
sortowanie przez wstawianie
Wyjaśnienie
W programowaniu stabilność algorytmu sortowania oznacza, że jeśli dwa elementy mają taką samą wartość, to po posortowaniu zachowają swoją pierwotną kolejność względem siebie.
Sortowanie szybkie (Quicksort) nie gwarantuje takiego zachowania, dlatego jest algorytmem niestabilnym. W trakcie dzielenia tablicy wokół tzw. pivota elementy o równych wartościach mogą przeskoczyć w taki sposób, że ich początkowa relacja zostanie zaburzona.
Dla kontrastu, algorytmy takie jak bąbelkowe, przez wstawianie czy przez zliczanie przy prawidłowej implementacji zachowują pierwotną kolejność jednakowych elementów, więc są stabilne.