Sortowanie

Sortowanie – jeden z podstawowych problemów informatyki, polegający 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, do działania których nie jest potrzebna większa niż stała pamięć dodatkowa (elementy sortowane przechowywane są przez cały czas w tablicy wejściowej), nazywane są algorytmami działającymi w miejscu.

Algorytmy sortujące, które dla elementów o tej samej wartości zachowują w tablicy końcowej kolejność tablicy wejściowej, nazywamy algorytmami stabilnymi.

Problem sortowania 
Formalna definicja problemu sortowania
 Dane wejściowe: ciąg  liczb 
 Wynik: permutacja (zmiana uporządkowania)  ciągu wejściowego taka, że

Klasyfikacja 
Algorytmy sortowania są zazwyczaj klasyfikowane według:
 złożoności (pesymistyczna, oczekiwana) – zależność liczby wykonanych operacji w stosunku od liczebności sortowanego zbioru  Typową, dobrą złożonością jest średnia  i pesymistyczna  Idealną złożonością jest  Algorytmy sortujące nie przyjmujące żadnych wstępnych założeń dla danych wejściowych wykonują co najmniej  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 
 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  i  o tym samym kluczu, jeśli  wystąpiło przed  to po sortowaniu stabilnym  nadal będzie przed 

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  elementó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  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  oznacza liczbę elementów do posortowania,  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) – 
 sortowanie przez wstawianie (ang. insertion sort) – 
 sortowanie przez scalanie (ang. merge sort) –  wymaga  dodatkowej pamięci
 sortowanie przez zliczanie (ang. counting sort lub count sort) –  wymaga  dodatkowej pamięci
 sortowanie kubełkowe (ang. bucket sort) –  wymaga  dodatkowej pamięci
 sortowanie pozycyjne (ang. radix sort) –  gdzie  to wielkość domeny cyfr, a  szerokość kluczy w cyfrach. Wymaga  dodatkowej pamięci
 sortowanie biblioteczne (ang. library sort) –  pesymistyczny

Niestabilne 
 sortowanie przez wybieranie (ang. selection sort)  – może być stabilne po odpowiednich zmianach
 sortowanie Shella – (ang. shellsort) złożoność nieznana;
 sortowanie grzebieniowe – (ang. combsort) optymistyczny  pesymistyczny 
 sortowanie szybkie – (ang. quicksort)  pesymistyczny 
 sortowanie introspektywne – (ang. introspective sort lub introsort) 
 sortowanie przez kopcowanie – (ang. heapsort)

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

Zobacz też 
 algorytm
 przeszukiwanie liniowe
 sortowanie zewnętrzne

Przypisy

Bibliografia

Linki zewnętrzne 
 
 

Algorytmika