Sortowanie pozycyjne

Wprowadzenie

Sortowanie pozycyjne (radix sort) stosowane jest do sortowania elementów, które składają się z szeregu pozycji (mogą to być liczby, gdzie pozycjami są poszczególne cyfry; wyrazy - w tym przypadku są to poszczególne litery; mogą to także być inne dane, np. daty). Zostało wynalezione prawdopodobnie w 1929 r. przez L. J. Comrie'a. Algorytm ten wymaga użycia innego algorytmu sortowania podczas swego działania, co ważne sortowanie to musi być stabilne. Gdy jako dodatkowego algorytmu sortowania użyjemy sortowania przez zliczanie to algorytm sortowania pozycyjnego działa w czasie O(n).

Przykład

Rozważmy następujący ciąg liczb do posortowania:

Intuicja podpowiada nam, aby posortować te liczby według najbardziej znaczącej cyfry, tzn. pierwszej od lewej. Jednakże potem musielibyśmy rekurencyjnie posortować liczby, które mają najbardziej znaczącą cyfrę taką samą według drugiej najbardziej znaczącej cyfry (w tym przypadku środkowej). Metoda taka wymaga dodatkowej pamięci. Jednakże moglibyśmy sortowanie zacząć od drugiej strony, czyli sortować od cyfry najmniej znaczącej. W wyniku posortowania w/w liczb według najmniej znaczącej cyfry otrzymujemy:

Cyfry według których zostały posortowane liczby powyżej są podkreślone. Tak posortowane liczby sortujemy następnie według drugiej najmniej znaczącej cyfry, czyli w tym przypadku środkowej. W ten sposób otrzymujemy:

Proszę zwrócić uwagę, że gdyby nie brać pod uwagę najbardziej znaczących cyfr to podane liczby byłyby już posortowane. Posortujmy je jeszcze według najbardziej znaczącej cyfry, czyli liczby setek:

Liczby są już posortowane. Do podanego sortowania pozycyjnego użyliśmy trzech sortowań pomocniczych (z tylu bowiem cyfr składały się liczby). W przypadku liczb i wyrazów do sortowań pomocniczych polecam użycie sortowania przez zliczanie.

Pojawia się w tym momencie problem - co zrobić, aby posortować liczby składające się z różnej ilości cyfr? Nic trudnego - wystarczy popatrzyć na przykład powyżej, a w szczególności na liczbę 055. Po prostu dopisujemy do każdej z liczb odpowiednią ilość zer po lewej stronie, tak by składały się one z tylu cyfr, ile ma liczba, która ma ich najwięcej w danym ciągu. W tym przypadku trzeba było dopisać tylko jedno 0, aby liczba 55 stała się liczbą 3-cyfrową (055).

Sortowanie wyrazów

Z sortowaniem wyrazów jest podobnie jak z sortowaniem liczb. W tym przypadku pozycjami są poszczególne litery danego wyrazu. Jednakże jest pewna różnica jeśli chodzi o sortowanie wyrazów różnej długości. W tym przypadku odpowiednią ilość znaków dopisujemy za wyrazem, a nie jak to było w przypadku liczb - przed. Znak ten musi być traktowany jako wyżej w alfabecie, niż wszystkie inne - może to być na przykład spacja.

Inne zastosowania

Sortowanie pozycyjne stosuje się nie tylko do sortowania liczb, czy wyrazów. W ten sposób możemy także sortować np. daty. Musimy jednak pamiętać, aby sortować od pozycji najmniej znaczących. W przypadku dat - najpierw sortujemy je według dni, potem według miesięcy, a na końcu według lat.

Sortowanie pozycyjne możemy także zastosować do sortowania rekordów baz danych. Na przykład chcemy posortować książkę telefoniczną według nazwisk, a w razie gdyby się one powtarzały to według imion, a w przypadku identyczności imion i nazwisk według numeru telefonu. Aby otrzymać taki wynik powinniśmy tą książkę telefoniczną posortować najpierw według numeru telefonu, potem według imion, a na końcu według nazwisk. Złożoność obliczeniowa takiego sortowania pozycyjnego na pewno nie będzie O(n). Wynika to z tego, że do posortowania np. nazwisk trudno jest użyć sortowania przez zliczanie.