Sortowanie pozycyjne jest pewnym algorytmem sortowania przez rozrzucanie stosowanym przy porządkowaniu np. kart bibliotecznych (np. ze względu na nazwisko autora), poczty (np. ze względu na kod pocztowy). Algorytm ten był używany do sortowania kart perforowanych służących do przechowywania danych, w dawnych komputerach.  Karta składała się z 80 kolumn, z których każda miała 12 pozycji. Kolumna służyła do zapamiętania jednej cyfry przez wybicie dziurki na odpowiedniej pozycji, zatem na jednej karcie można było zapamiętać słowo 80 znakowe. Maszyna sortująca, automatycznie rozdzielała karty do 12 pojemników w zależności od położenia dziurki w ustalonej kolumnie. Następnie, należało wyjąć karty z kolejnych pojemników tworząc jeden plik kart i ponownie użyć maszyny sortującej do rozdzielenia kart ze względu na następną kolumnę.

Można sądzić, że zadania sortowania liczb w systemie dziesiętnym można wykonać stosując podobną zasadę: posortować najpierw dany zbiór liczb, ze względu na najbardziej znaczącą cyfrę, np. tworząc rodzinę zbiorów liczb o takiej samej pierwszej cyfrze. Połączyć wszystkie kubełki tworząc ponownie jeden ciąg i powtórzyć proces rozrzucania, ale biorąc tym razem pod uwagę następną cyfrę rozważanych liczb. Czy postępowanie takie można jednak zastosować do dowolnego ciągu liczb naturalnych? 

Przykład 5.1

Chcemy posortować następujący ciąg liczb 94, 572, 321, 58. Postąpimy tak, jak w opisanej wyżej metodzie. W kolejnych krokach otrzymamy:

1. krok: 321, 572, 58, 94, jako wynik sortowania ze względu na najbardziej znaczącą cyfrę.
2. krok: 321, 94, 572, 58, jako wynik sortowania, ze względu na drugą z kolei cyfrę.
3. krok: 321, 572, 94, 58, jako wynik sortowania ze względu na trzecią cyfrę.

Wynik nie jest, niestety, ciągiem uporządkowanym niemalejąco. Jest oczywiste, że powodem naszego niepowodzenia jest niejednakowa liczba cyfr w rozważanych liczbach.

Niech zatem będzie dany ciąg liczb całkowitych d cyfrowych. Metoda zastosowana w algorytmie RadixSort jest bardzo podobna do wspomnianej powyżej metody, ale zaczynamy sortowanie od najmniej znaczącej cyfry. Aby posortować ciąg liczb całkowitych w systemie dziesiętnym tworzymy 10 pojemników, tzw. "kubełków" odpowiadających cyfrom 0,...,9. Każda liczba wpada najpierw do "kubełka" o numerze równym jej ostatniej cyfrze. Następnie liczby są wyjmowane kolejno z "kubełków" 0,1,2... aby utworzyć jeden ciąg. Teraz proces należy powtórzyć, z tym, że "rozrzucając"  liczby, bierzemy pod uwagę drugą od końca cyfrę, itd.

Aby wynik algorytmu był zawsze poprawny trzeba zwrócić uwagę na sposób reprezentacji "kubełków". Gdybyśmy je zaimplementowali jako stosy, to mogłoby się zdarzyć tak jak w przykładzie 5.2

Przykład 5.2

Dany jest ciąg  253, 523, 235, 532, 325, 352, 252, 525, 718. Elementy wewnątrz "kubełków"  będziemy układali na stosie. Pamiętamy, że każdy nowy element trafia na szczyt stosu i zdejmujemy elementy najpierw ze szczytu stosu.

W pierwszym etapie rozrzucania bierzemy pod uwagę tylko ostatnią cyfrę. Zauważmy, że niektóre "kubełki" są puste, np. "kubełek" o numerze 1 jest pusty, bo nie było w naszym ciągu żadnej liczby kończącej się jedynką. Po pierwszym rozrzucaniu i po po połączeniu "kubełków" otrzymaliśmy następujący ciąg :252, 352, 532, 523, 253, 525, 325, 235, 718.  Teraz powtarzamy rozrzucanie ze względu na drugą cyfrę. Tak jak poprzednio elementy w "kubełkach" kładziemy jeden nad drugim. Po  zdjęciu elementów kolejno ze stosów o numerach 1, 2, 3, 5 ( bo tylko te stosy były niepuste) otrzymaliśmy ciąg 718, 325, 525, 523, 235, 532, 253, 352, 252. Teraz następuje trzeci etap, rozrzucanie ze względu na najbardziej znaczącą cyfrę.  Po połączeniu "kubełków" otrzymujemy ciąg: 252, 253, 235, 352, 325, 532, 525, 718, który nie jest niestety uporządkowany niemalejąco.

Kłopot polega na tym, że elementy są zdejmowane ze stosu w kolejności odwrotnej do tej, w jakiej były wkładane na stos.  Taki  problem nie wystąpi, jeżeli zamiast stosów użyjemy kolejek. J

Przykład 5.3

Rozważmy ciąg z przykładu  5.2 : 253, 523, 235, 532, 325, 352, 252, 525, 718. W tabeli poniżej przedstawiliśmy kolejne etapy  algorytmu.

Tym razem "kubełki" są realizowane jako kolejki, do których elementy wpadają zawsze na koniec, a wyjmowane są zawsze najpierw początkowe elementy. W tabeli, dla uproszczenia,  przedstawiliśmy tylko te kolejki,  które w danym etapie algorytmu były niepuste. Tym razem wynikiem trzeciego etapu algorytmu jest ciąg uporządkowany niemalejąco. J

Szkic algorytmu

Niech e[1], ..., e[n] będzie tablicą elementów do posortowania. Załóżmy, że kolejki q[0], q[1],..., q[9] są początkowo puste.

Poprawność algorytmu RadixSort

Załóżmy, że w wyniku k-1 pierwszych iteracji, elementy tablicy e tworzą ciąg uporządkowany niemalejąco, jeśli rozważać tylko k-1 ostatnich pozycji każdej z liczb.  Prześledzimy zachowanie algorytmu w k-tym przebiegu. Niech x i y będą dowolnymi elementami tablicy e i niech:

x = x_k+1 10 ^k+1 + x_k 10^k + x*

y = y_k+1 10 ^k+1 + y_k 10^k + y*

gdzie x* i y* są liczbami mniejszymi od 10^k oraz x poprzedza y w tablicy e (tzn. x* £ y*). Rozważymy trzy przypadki ze względu na relację zachodzącą między k-tymi cyframi rozwinięcia dziesiętnego liczb x i y:

1. Albo x_k = y_k i wtedy liczby x, y znajdą się w k-tym przebiegu w tej samej kolejce, ale x zostanie w niej umieszczone wcześniej niż y i dlatego, po połączeniu kolejek, x będzie poprzedzało y.

2. Albo  x_k < y_k  i wtedy x trafi do kolejki o mniejszym numerze niż y, zgodnie z zasadą rozrzucania. Ponieważ łączenie kolejek nastąpi też w kolejności rosnących numerów kolejek, zatem po k-tym przebiegu x będzie poprzedzało y po połączeniu kolejek.

3. Albo x_k > y_k. W takim przypadku y zostanie wpisane do kolejki o numerze wcześniejszym niż numer kolejki, do której wpadnie x. Gdy kolejki zostaną połączone y będzie poprzedzało x.

Zatem we wszystkich trzech przypadkach liczby x i y będą występowały we właściwej kolejności. Po k-tej iteracji otrzymany ciąg e jest uporządkowany niemalejąco ze względu na k ostatnich pozycji.

Biorąc pod uwagę udowodniony powyżej niezmiennik, po d iteracjach, tablica e zawiera uporządkowane niemalejąco elementy początkowego ciągu.

Koszt algorytmu RadixSort

Operacjami dominującymi w tym algorytmie są operacje wkładania i usuwania elementu do kolejki. W każdym przebiegu pętli zewnętrznej wykonujemy Q(n) tego typu operacji. Koszt całkowity algorytmu zastosowanego do ciągu n liczb d-cyfrowych wynosi Q(n ´ d).  Jeżeli d jest stałą, to koszt algorytmu jest liniowy.

Algorytm RadixSort można też przedstawić w uogólnionej postaci następująco:

Zwykle, w treści pętli tego algorytmu występuje algorytm CountingSort, który jest algorytmem stabilnym i łatwym do zaimplementowania. I chociaż wymaga on w przypadku ogólnym dodatkowej tablicy, to w tym zastosowaniu, do sortowania pozycyjnego, jego tablica pomocnicza jest dziesięcioelementowa (pozycje tej tablicy odpowiadają cyfrom).

Uwaga 1. Algorytm RadixSort można stosować również do sortowania liczb o różnej długości, np. uzupełniając "brakujące" pozycje początkowe zerami. 2. Można też go stosować do sortowania dowolnych rekordów, których składowe należą do dowolnych liniowo uporządkowanych zbiorów skończonych.

Pytanie 6: Załóżmy, że alfabet składa się z 25 liter oraz, że mamy posortować 1000 słów 5 literowych. Ile kolejek musimy utworzyć w procesie sortowania tych słów i ile razy wykonamy operację wkładania elementu do kolejki?

« poprzedni punkt

następny punkt »