algorithm
Sortowanie
Szukaj…
Parametry
| Parametr | Opis |
|---|---|
| Stabilność | Algorytm sortowania jest stabilny, jeśli zachowuje względną kolejność równych elementów po sortowaniu. |
| W miejscu | Algorytm sortowania jest stosowany, jeśli sortuje przy użyciu tylko pamięci pomocniczej O(1) (nie licząc tablicy, którą należy posortować). |
| Najlepsza złożoność przypadku | Algorytm sortowania ma najlepszą złożoność czasu przypadku O(T(n)) jeśli jego czas działania wynosi co najmniej T(n) dla wszystkich możliwych danych wejściowych. |
| Średnia złożoność sprawy | Algorytm sortowania ma średnią złożoność czasu obserwacji O(T(n)) jeśli jego czas działania, uśredniony dla wszystkich możliwych danych wejściowych , wynosi T(n) . |
| Najgorsza złożoność przypadku | Algorytm sortowania ma najgorszą złożoność czasu O(T(n)) jeśli jego czas działania wynosi co najwyżej T(n) . |
Stabilność w sortowaniu
Stabilność w sortowaniu oznacza, czy algorytm sortowania zachowuje względną kolejność kluczy równych oryginalnym wejściom w wynikowym wyniku.
Mówi się, że algorytm sortowania jest stabilny, jeśli dwa obiekty z jednakowymi kluczami pojawią się w tej samej kolejności na posortowanym wyjściu, tak jak pojawiają się w nieposortowanej tablicy wejściowej.
Rozważ listę par:
(1, 2) (9, 7) (3, 4) (8, 6) (9, 3)
Teraz posortujemy listę według pierwszego elementu każdej pary.
Stabilne sortowanie tej listy spowoduje wyświetlenie poniższej listy:
(1, 2) (3, 4) (8, 6) (9, 7) (9, 3)
Ponieważ (9, 3) pojawia się również po (9, 7) na oryginalnej liście.
Niestabilne sortowanie spowoduje wyświetlenie poniższej listy:
(1, 2) (3, 4) (8, 6) (9, 3) (9, 7)
Sortowanie niestabilne może generować taki sam wynik jak sortowanie stabilne, ale nie zawsze.
Dobrze znane rodzaje stabilne:
Znane rodzaje niestabilne: