Sortowanie – jeden z podstawowych problemów informatyki . Polega na uporządkowaniu zbioru danych względem pewnych cech charakterystycznych każdego elementu tego zbioru . Szczególnym przypadkiem jest sortowanie względem wartości każdego elementu, np. sortowanie liczb, słów itp.

Algorytmy sortowania są stosowane w celu uporządkowania danych, umożliwienia stosowania wydajniejszych algorytmów (np. wyszukiwania) i prezentacji danych w sposób czytelniejszy dla człowieka.

Jeśli jest konieczne posortowanie zbioru większego niż wielkość dostępnej pamięci, stosuje się algorytmy sortowania zewnętrznego .

Klasyfikacja

Algorytmy sortowania są zazwyczaj klasyfikowane według:

• złożoności (pesymistyczna, oczekiwana i obliczeniowa) – zależność liczby wykonanych operacji w stosunku od liczebności sortowanego zbioru (n). Typową, dobrą złożonością jest średnia O(n log n) i pesymistyczna Ω(n²). Idealną złożonością jest O(n). Algorytmy sortujące nie przyjmujące żadnych wstępnych założeń dla danych wejściowych wykonują co najmniej O(n log n) operacji w modelu obliczeń, w którym wartości są "przezroczyste" i dopuszczalne jest tylko ich porównywanie (w niektórych bardziej ograniczonych modelach istnieją asymptotycznie szybsze algorytmy sortowania);
• złożoność pamięciowa
• sposób działania: algorytmy sortujące za pomocą porównań to takie algorytmy sortowania, których sposób wyznaczania porządku jest oparty wyłącznie na wynikach porównań między elementami; Dla takich algorytmów dolne ograniczenie złożoności wynosi Ω(n log n);
• stabilność: stabilne algorytmy sortowania utrzymują kolejność występowania dla elementów o tym samym kluczu (klucz – cecha charakterystyczna dla każdego elementu zbioru, względem której jest dokonywane sortowanie). Oznacza to, że dla każdych dwóch elementów R i S o tym samym kluczu, jeśli R wystąpiło przed S to po sortowaniu stabilnym R nadal będzie przed S;

Kiedy elementy o tym samym kluczu są nierozróżnialne, stabilność nie jest istotna.

Przykład: (para liczb całkowitych sortowana względem pierwszej wartości)

(4, 1) (3, 7) (3, 1) (5, 6)

W tym przypadku są możliwe dwa różne wyniki sortowania:

(3, 7) (3, 1) (4, 1) (5, 6) – kolejność zachowana(3, 1) (3, 7) (4, 1) (5, 6) – kolejność zmieniona

• Stabilne algorytmy sortowania gwarantują, że kolejność zostanie zachowana.
• Niestabilne algorytmy sortowania mogą zmienić kolejność.

Algorytmy sortujące dzielimy na proste ("naiwne") i zaawansowane ("logarytmiczne"). Powstanie lepszych niż proste algorytmów sortowania spowodowane było konsekwencjami poniższego faktu:

W losowym rozmieszczeniu n elemetów każdy element jest przesunięty względem swojej pozycji w posortowanym ciągu średnio o pozycji.

Jeżeli algorytm sortowania zamienia tylko elementy sąsiadujące ze sobą, musi dokonać średnio zamian dla każdego z n elementów. A więc średnia liczba porównań wynosi . Jedynym sposobem zmniejszenia asymptotycznej złożoności algorytmów sortujących jest wprowadzenie możliwości zamieniania elementów nie sąsiadujących ze sobą.

Przykładowe algorytmy sortowania

W podanej złożoności n oznacza liczbę elementów do posortowania, k liczbę różnych elementów.

Stabilne

Elementy o równej wartości będą występowały, po posortowaniu, w takiej samej kolejności jaką miały w zbiorze nieposortowanym.

• sortowanie bąbelkowe (ang. bubblesort) – O(n²)
• sortowanie przez wstawianie (ang. insertion sort) – O(n²)
• sortowanie przez scalanie (ang. merge sort) – O(nlogn), wymaga O(n) dodatkowej pamięci
• sortowanie przez zliczanie (ang. counting sort lub count sort) – O(n + k), wymaga O(n + k) dodatkowej pamięci
• sortowanie kubełkowe (ang. bucket sort) – O(n), wymaga O(k) dodatkowej pamięci
• sortowanie pozycyjne (ang. radix sort) – O(d(n + k)), gdzie k to wielkość domeny cyfr, a d szerokość kluczy w cyfrach. Wymaga O(n + k) dodatkowej pamięci
• sortowanie biblioteczne (ang. library sort) – O(nlogn), pesymistyczny O(n²)

Niestabilne

• sortowanie przez wybieranie (ang. selection sort) O(n²) – może być stabilne po odpowiednich zmianach
• sortowanie Shella – (ang. shellsort) złożoność nieznana;
• sortowanie grzebieniowe – (ang. combsort) złożoność nieznana;
• sortowanie szybkie – (ang. quicksort) Θ(nlogn), pesymistyczny O(n²); z wykorzystaniem algorytmu selekcji "mediana median" ("magicznych piątek") do wyszukiwania mediany, optymistyczna złożoność to O(nlogn),
• sortowanie introspektywne – (ang. introspective sort lub introsort) O(nlogn);
• sortowanie przez kopcowanie – (ang. heapsort) O(nlogn);

Podobne problemy

• wyszukiwanie elementu o największej wartości funkcji porządkującej
• wyszukiwanie n-tego elementu.

Zobacz też

• sortowanie zewnętrzne
• przeszukiwanie liniowe
• algorytm

Linki zewnętrzne

• Wizualizacja wielu algorytmów sortowania ( ang. ).