Algorytmy sortowania

Sortowanie 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.

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").

• Algorytm sortowania przez wstawienie
  Algorytm sortowania przez wstawianie wykorzystuje poszukiwanie liniowe w celu znalezienia miejsca wstawiania wybranego elementu na liście uporządkowanej. Element wybrany/porównywany może być większy bądź równy, elementowi z uporządkowanej listy, lub mniejszy.
  
  Sortowanie przez wstawienie to algorytm, którego średni czas działania wynosi O(n2). Jest on skuteczny dla małej ilości danych. Jest to jeden z prostszych i jeden z bardziej znanych algorytmów sortowania. Jest on stabilny i nie wymaga dodatkowej pamięci.


• Algorytm sortowania przez selekcję
  Metoda ta nazywana jest sortowaniem przez wymianę gdyż na początku szukany jest najmniejszy element, po znalezieniu go jest on zamieniany z pierwszym elementem tablicy.
  
  W najgorszym przypadku każdy element powoduje jednokrotne przestawienie wszystkich poprzedzających go elementów, a wtedy liczba porównań wynosi: n*(n-1). Liczba porównań zależna jest od początkowego rozmieszczenia elementów w tablicy.


• Algorytm sortowanie przez scalanie
  Ideą działania algorytmu jest dzielenie zbioru danych na mniejsze zbiory, aż do uzyskania n zbiorów jednoelementowych, które same z siebie są posortowane
  
  Algorytm ten w każdym przypadku osiąga złożoność T(n) = n*log(n). Niestety algorytm MergeSort posiada większą złożoność pamięciową, potrzebuje do swojego działania dodatkowej, pomocniczej struktury danych.


• Algorytm sortowania szybkiego
  Zasada jego działania opiera się o metodę dziel i zwyciężaj. Zbiór danych zostaje podzielony na dwa podzbiory i każdy z nich jest sortowany niezależnie od drugiego.
  
  Optymistyczna złożoność obliczeniowa sortowania szybkiego wynosi O(n log n) i jest to jeden z najszybszych algorytmów sortujących (a na pewno najbardziej znany). Doskonale radzi sobie z sortowaniem wielkich tablic i został włączony do standardowej biblioteki języka C.


• Algorytm sortowania stogowego
  W zbiorze tworzymy kopiec, a następnie dokonujemy jego rozbioru. W wyniku wykonania tych dwóch operacji zbiór zostanie posortowany.
  
  Algorytm jest ciekawy z racji faktu, iż jest on szybki oraz nie pochłania zbyt wiele zasobów pamięci. Podstawową zaletą algorytmu jest to, że do stworzenia kopca wykorzystać można tę samą tablicę, w której początkowo znajdują się nieposortowane elementy. Dzięki temu uzyskuje się stałą złożoność pamięciową.