Początki sortowania pozycyjnego sięgają XIX wieku. W roku 1890 do opracowania spisu ludności Stanów Zjednoczonych po raz pierwszy zastosowano maszynę licząco‑analityczną. Jej prototyp został zbudowany w 1887 roku przez amerykańskiego inżyniera i wynalazcę Hermana Holleritha.

R18gYKRa2sxqT

Rysunek przedstawia maszynę licząco‑analityczną. Widoczne są zegary oraz tablica z otworami. Przy części biurkowej znajdują się matryce. Na rysunku zapisano, że została opatentowana w styczniu 1889 roku.

Idea algorytmu sortowania pozycyjnego

W wypadku sortowania pozycyjnego nie porównuje się ze sobą wprost całych liczb zapisanych w tablicy wejściowej. Elementy są porządkowane ze względu na cyfry umieszczone na tych samych pozycjach.

Proces sortowania rozpoczynamy od najmniej znaczących cyfr jedności i kontynuujemy do chwili, w której posortujemy liczby kolejno według wszystkich cyfr, kończąc na tej najbardziej znaczącej (kolejno: jedności, dziesiątki, setki itd.). Do posortowania liczb według cyfr na danej pozycji możemy użyć dowolnego stabilnego algorytmu sortowaniasortowanie stabilnestabilnego algorytmu sortowania.

Na początek rozważamy cyfry jedności. Sortujemy więc liczby za pomocą dowolnego algorytmu stabilnego tak, aby były ustawione niemalejąco według ostatniej cyfry. Wynikiem pierwszego kroku będzie poniższa tablica.

W kolejnym kroku ponownie stabilnie sortujemy tablicę, tym razem według cyfr dziesiątek.

Podczas ostatniej iteracji będziemy rozważać cyfry setek.

Ostatecznie tablica wynikowa zawierająca liczby posortowane niemalejąco przedstawia się następująco:

AIndeks dolny 1₁= {9, 12, 24, 60, 68, 140, 512}

Pseudokod

Poniżej została przedstawiona funkcja w pseudokodzie realizująca sortowanie pozycyjne. Wynikiem jej działania jest uporządkowana niemalejąco tablica wartości. Funkcja przyjmuje dwa argumenty: tablicaSortowana - czyli tablica do posortowania oraz liczbaCyfr - czyli wartość wskazująca, ile cyfr posiada największa liczba w tablicy.

funkcja sortowaniePozycyjne(tablicaSortowana, liczbaCyfr)
	dla i = liczbaCyfr-1, liczbaCyfr-2, ..., 0 wykonuj
		posortuj stabilnie wartości w tablicy tablicaSortowana według i-tej pozycji

Sortowanie według i-tej pozycji oznacza, że dla i równego liczbaCyfr‑1 bierzemy cyfrę jedności, dla i równego liczbaCyfr‑2 cyfrę dziesiątek - i tak dalej, aż do i równego 0, gdzie bierzemy najbardziej znaczącą cyfrę w liczbie. Dla liczb, które nie posiadają cyfry na danej pozycji, przyjmujemy, że znajduje się tam cyfra 0.

Algorytm sortowania pozycyjnego z wykorzystaniem sortowania kubełkowego

Algorytm sortowania kubełkowego został dokładnie omówiony w e‑materiale Sortowanie kubełkowePPpmzST7zSortowanie kubełkowe.

Proces sortowania można wyobrazić sobie jako umieszczanie elementów zbioru w kubełkach, które odpowiadają cyfrom systemu liczbowegosystem liczbowysystemu liczbowego. W przypadku systemu dwójkowego do dyspozycji mamy dwa kubełki oznaczone jako 0 i 1; dla systemu dziesiętnego jest ich dziesięć – oznaczają one cyfry od 0 do 9.

Porządkowanie zaczyna się od sprawdzenia cyfr jedności. Liczby zakończone cyfrą 0 trafiają do kubełka oznaczonego symbolem 0, te zakończone cyfrą 1 – do kubełka z numerem 1, a kończące się cyfrą 2 – do kubełka oznaczonego jako 2 itd.

Po ułożeniu wszystkich elementów w pojemnikach wyjmujemy liczby z kubełków. Zaczynamy od kontenera oznaczonego symbolem 0, następnie przechodzimy do kubełka z numerem 1, później 2 - i tak do końca.  Liczby opuszczają pojemniki w takiej kolejności, w jakiej zostały do nich włożone.

Wyjmowane kolejno elementy umieszczamy w nowym zbiorze i powtarzamy dla niego opisane czynności. Tym razem sprawdzamy cyfry o wagach większych o 1. Wagą pozycji są kolejne potęgi podstawy systemu liczbowego, w jakim liczba jest zapisana. Elementy znowu trafiają do kubełków, a później jeszcze raz są z nich wyjmowane i tworzą następny zbiór.

Postępujemy tak do momentu, gdy posortujemy liczby według cyfr odpowiadających największym wagom.

Podczas sortowania posłużymy się systemem dziesiętnym. Potrzebnych jest nam zatem 10 kubełków dla cyfr od 0 do 9. Porządkowanie zaczynamy od cyfr jedności      (o wagach 10Indeks górny 0⁰):

Potem zapisujemy liczby znajdujące się w kubełkach ponumerowanych od 0 do 9. Pamiętajmy przy tym, aby elementy opuszczały kubełki w takiej kolejności, w jakiej były w nich umieszczane. W rezultacie otrzymujemy następujący zbiór:

AIndeks dolny 1₁= {100, 660, 321, 512, 833, 333, 584, 997, 268, 69}

Następnie powtarzamy opisane czynności – tym razem bierzemy pod uwagę cyfry dziesiątek (o wagach 10Indeks górny 1¹):

Ponownie zapisujemy liczby z poszczególnych kubełków:

AIndeks dolny 2₂= {100, 512, 321, 833, 333, 660, 268, 69, 584, 997}

Wszystkie liczby w przykładowym zbiorze są najwyżej trzycyfrowe. Pozostał więc jeszcze jeden cykl operacji. Zauważmy, że wśród elementów znajduje się liczba dwucyfrowa – w jej przypadku brakującą pozycję (odpowiadającą wadze 10Indeks górny 2²) zastępujemy cyfrą 0.

Po raz ostatni odczytujemy elementy zapisane w kontenerach. Otrzymana tablica wynikowa jest posortowana rosnąco:

AIndeks dolny 3₃= {69, 100, 268, 321, 333, 512, 584, 660, 833, 997}

Zapis w pseudokodzie

Zapoznajmy się teraz z implementacją algorytmu zapisaną w postaci pseudokodu.

Specyfikacja:

Dane:

• liczbaElementow – liczba naturalna; długość tablicy z danymi

• liczbaCyfr – liczba naturalna; liczba cyfr tworzących największą liczbę z tablicy

• tablica[0..liczbaElementow‑1][0..liczbaCyfr‑1] – dwuwymiarowa tablica liczb naturalnych; dane do posortowania

Wynik:

• tablica[0..liczbaElementow‑1][0..liczbaCyfr‑1] – posortowana niemalejąco tablica liczb naturalnych

Tablica kubełki[0..9] służy do tymczasowego zapamiętania liczb znajdujących się w kubełku odpowiadającym sprawdzanej obecnie cyfrze.

dla d = liczbaCyfr-1, liczbaCyfr-2, ..., 0 wykonuj
	dla n = 0, 1, ..., liczbaElementow-1 wykonuj
		cyfra ← tablica[n][d]
		umieść wewnątrz kubełki[cyfra] wartość tablica[n]
	x ← 0
	dla n = 0, 1, ..., 9 wykonuj
		dopóki kubełki[n] zawiera liczby wykonuj
			liczba ← wyjmij liczbę z kubełka kubełki[n]
			tablica[x] ← liczba
			x ← x + 1

Ogólny algorytm sortowania pozycyjnego możemy przedstawić w następujący sposób:

posortuj_pozycyjnie(tablica_nieuporządkowana)
	dla każdej pozycji elementu tablicy, w kolejności od najmniej znaczącej do najbardziej znaczącej, wykonaj
		utwórz kubełki dla każdego znaku (wartości), który może wystąpić
		wykonaj sortowanie kubełkowe tablicy według tych znaków (wartości)
		dla kolejnych kubełków
			przenieś elementy z kubełka na koniec porządkowanego ciągu w takiej samej kolejności, w jakiej były w nim umieszczane
	zwróć uporządkowany ciąg

Własności sortowania pozycyjnego

Złożoność obliczeniowa zaprezentowanego algorytmu zależy w dużym stopniu od tego, z ilu cyfr składają się liczby zapisane w sortowanej tablicy.

Algorytm sortowania pozycyjnego jest algorytmem stabilnym, co oznacza, że elementy o równej wartości po posortowaniu będą pojawiać się w takiej samej kolejności jak w nieposortowanym zbiorze.

W przypadku sortowania pozycyjnego wykonuje się tyle cykli operacji, ile cyfr użyto do zapisania największej liczby w sortowanym zbiorze (przyjmijmy, że liczbę cyfr oznaczymy jako d). Całkowita złożoność czasowa będzie zależeć od użytego dodatkowego algorytmu sortowania (oznaczmy złożoność dodatkowego algorytmu jako m). Złożoność czasowa wynosi więc O(dm).

W przypadku użycia sortowania kubełkowego, w każdym przebiegu sprawdzane są wszystkie elementy tablicy (o rozmiarze n), a następnie pobierana jest zawartość każdego z k kubełków. Złożoność obliczeniowa algorytmu wynosi zatem O(d(n + k)).

Zwiększenie liczby kubełków skutkuje zmniejszeniem liczby potrzebnych cyfr (im większa jest wartość k, tym mniejsze jest d). W rezultacie skraca się czas potrzebny do zrealizowania algorytmu.

Zastosowanie sortowania pozycyjnego

Sortownie pozycyjne rzadko wykorzystywane jest w praktyce. Dobrze się sprawdza, gdy należy uporządkować zbiór liczb całkowitych podobnych do siebie (mających np. taką samą liczbę cyfr bądź rozpoczynających się od identycznych ciągów cyfr) albo należących do niewielkiego przedziału. Metoda ta jest z kolei trudna do zastosowania w przypadku porządkowania liczb zmiennoprzecinkowychliczba zmiennoprzecinkowaliczb zmiennoprzecinkowych.

Po zmodyfikowaniu algorytm sortowania pozycyjnego może być z powodzeniem stosowany do znajdowania duplikatów w tablicy.

Słownik