Stabilność sortowania oznacza, że algorytm zachowuje pierwotną kolejność elementów o takich samych kluczach sortowania.
Jeżeli dwa elementy mają tę samą wartość porównywaną, to po sortowaniu stabilnym pozostaną w takiej samej kolejności, w jakiej były przed sortowaniem.
Przykład
Mamy listę osób sortowaną według wieku:
Anna 20
Jan 18
Ewa 20
Po stabilnym sortowaniu według wieku otrzymamy:
Jan 18
Anna 20
Ewa 20
Anna nadal jest przed Ewą, ponieważ przed sortowaniem też była przed nią, a obie osoby mają ten sam wiek.
Dlaczego stabilność jest ważna?
Stabilność ma znaczenie szczególnie wtedy, gdy sortujemy dane wieloetapowo, np. najpierw według imienia, a potem według klasy lub daty. Stabilny algorytm pozwala zachować wcześniejszy porządek dla elementów równych w kolejnym sortowaniu.
Przykłady algorytmów stabilnych
- sortowanie bąbelkowe,
- sortowanie przez wstawianie,
- sortowanie przez zliczanie, jeśli jest poprawnie zaimplementowane,
- sortowanie przez scalanie.
Przykłady algorytmów niestabilnych
- sortowanie szybkie w typowej implementacji,
- sortowanie przez wybieranie,
- sortowanie przez kopcowanie.
W pytaniach egzaminacyjnych często wystarczy pamiętać, że sortowanie szybkie zwykle nie jest stabilne.