Podstawy sortowania

WPROWADZENIE

Sortowaniem nazywamy proces ustawiania zbioru obiektów w określonym porządku [Wirth]. Sortowanie stosuje się w celu ułatwienia późniejszego wyszukiwania elementów sortowanego zbioru.

SPECYFIKACJA
Problem sortowania [Cormen].

DANE WEJŚCIOWE
Ciąg n liczb (a_1, a_2, ..., a_n).

DANE WYJŚCIOWE
Permutacja (zmiana kolejności) (a_1', a_2', ..., a_n')
ciągu wejściowego taka, że a_1' <= a_2' <= ... <= a_n'.

Podział metod sortowania:

• Sortowanie tablic (sortowanie wewnętrzne). Dane są przechowywane w szybkiej, ale ograniczonej pamięci o dostępie swobodnym. Znamy liczbę elementów. Sortowanie powinno być wykonane in situ (w miejscu, in place).
• Sortowanie plików sekwencyjnych (sortowanie zewnętrzne). Dane są przechowywane w powolnej, ale pojemnej pamięci zewnętrznej o dostępie sekwencyjnym. Nie znamy liczby przetwarzanych elementów, ale na końcu ciągu umieszczamy wyróżniony element, wartownika, który nie należy do tego zbioru. Czasem wartownik pełni rolę ogólniejszą niż tylko zakończenie zbioru.

Algorytmy sortowania są zazwyczaj klasyfikowane według kilku kryteriów.

• Złożoność czasowa (pesymistyczna, oczekiwana) - zależność liczby wykonanych operacji w stosunku do liczebności sortowanego zbioru (n).
• Złożoność pamięciowa.
• Sortowanie stabilne albo niestabilne.
• Sortowanie adaptacyjne (polega na wykonywaniu różnych sekwencji operacji dla różnych układów danych) albo nieadaptacyjne (sekwencja wykonywanych operacji nie zależy od kolejności danych).

MODELE SORTOWANIA

Podstawowy model sortowania polega na porównywaniu całych kluczy w celu ustalenia, który jest większy. Mamy teoretyczne ograniczenie na złożoność czasową O(n log n). Czasem można zastosować inne podejście.

W sortowaniu pozycyjnym na raz przetwarza się fragmenty kluczy, a nie całe klucze [radix sort]. Przykładem może być sprawdzanie kolejnych cyfr liczby naturalnej lub znaków w napisie. Można zaczynać sortowanie od cyfr najbardziej znaczących lub najmniej znaczących.

Jeżeli klucze należą do skończonego zbioru k-elementowego, to zamiast porównywania kluczy można zliczać wystąpienia kolejnych kluczy [counting sort]. Złożoność czasowa to O(n+k), złożoność pamięciowa to O(k) [klucze nierozróżnialne] lub O(n+k) [klucze rozróżnialne, to jest właściwie sortowanie bukietowe, bucket sort].

STABILNOŚĆ

Metodę sortowania nazywamy stabilną, jeżeli podczas procesu sortowania pozostaje nie zmieniony względny porządek obiektów o identycznych kluczach. Przykład: alfabetyczna lista nazwisk uczniów sortowana wg ocen.

Przykład sortowania par liczb całkowitych względem pierwszej wartości.
(4, 1) (3, 7) (3, 1) (5, 6) - oryginalna kolejność
(3, 7) (3, 1) (4, 1) (5, 6) - kolejność zachowana (stabilność)
(3, 1) (3, 7) (4, 1) (5, 6) - kolejność zmieniona (brak stabilności)

PRZYKŁADOWE ALGORYTMY STABILNE

n to liczba elementów do posortowania, k to liczba różnych elementów.

• Sortowanie bąbelkowe (ang. bubblesort) - czas O(n^2), dodatkowa pamięć O(1).
• Sortowanie przez wstawianie (ang. insertion sort) - czas O(n^2), dodatkowa pamięć O(1).
• Sortowanie przez scalanie (ang. merge sort) - czas O(n log n), wymaga O(n) dodatkowej pamięci.
• Sortowanie przez zliczanie (ang. counting sort lub count sort) - czas O(n + k), wymaga O(n + k) dodatkowej pamięci.
• Sortowanie kubełkowe (ang. bucket sort) - czas O(n), wymaga O(k) dodatkowej pamięci.
• Sortowanie pozycyjne (ang. radix sort) - czas 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) - czas O(n log n), pesymistyczny O(n^2).
• Sortowanie algorytmem timsort stosowanym w Pythonie.

PRZYKŁADOWE ALGORYTMY NIESTABILNE

• Sortowanie przez wybieranie (ang. selection sort) - czas O(n^2), 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) - czas O(n log n), pesymistyczny O(n^2), z wykorzystaniem algorytmu selekcji "mediana median" ("magicznych piątek") do wyszukiwania mediany, optymistyczna złożoność to O(n log n).
• Sortowanie introspektywne (ang. introspective sort lub introsort) - czas O(n log n).
• Sortowanie przez kopcowanie (ang. heapsort) - czas O(n log n).