Sortowanie pozycyjne

Sortowanie pozycyjne (ang. radix sort) to algorytm sortowania porządkujący stabilnie ciągi wartości (liczb, słów) względem konkretnych cyfr, znaków itp, kolejno od najmniej znaczących do najbardziej znaczących pozycji. Złożoność obliczeniowa jest równa $O(d(n+k)),$ gdzie $k$ to liczba różnych cyfr, a $d$ liczba cyfr w kluczach. Wymaga $O(n+k)$ dodatkowej pamięci.

Przewagą sortowania pozycyjnego nad innymi metodami jest fakt, iż nie wykonuje ono żadnych operacji porównania na danych wejściowych. Załóżmy, że mamy dużą liczbę bardzo długich liczb, bardzo do siebie podobnych – w tym sensie, że większość z nich ma takie same cyfry na początkowych pozycjach. Nie jest łatwo powiedzieć która jest większa, gdyż za każdym razem musimy porównać dużo cyfr, zanim trafimy na różnicę. Czas porównania takich liczb jest zatem proporcjonalny do ich długości. Gdybyśmy do posortowania tych liczb zastosowali algorytm porównujący liczby, np. sortowanie szybkie, otrzymalibyśmy dla niego złożoność $O(dn\log n)$ gdzie $d$ to liczba cyfr w liczbach.

Dla krótkich ciągów efektywniejsze jest sortowanie przez zliczanie.

Algorytmy pozycyjne sprawdzają się także w roli algorytmów sortujących listy.

Implementacja w pseudojęzyku programowania

• tab[] – tablica ciągów (cyfr, liter itp.) gdzie pozycja 1 oznacza najbardziej znaczącą pozycje ciągu
• d – długość ciągów

procedure RadixSort(tab[],d)
begin
   for i:=d downto 1 do
       posortuj stabilnie ciągi według i-tej pozycji;
end;

Dowód poprawności algorytmu sortowania pozycyjnego

Załóżmy, że przed i-tym przebiegiem pętli for, wszystkie ciągi są posortowane według (i-1)tej cyfry/litery. Po kolejnej iteracji ciągi będą posortowane według i-tej. Jeżeli dla dwóch, lub więcej ciągów, ich i-ta cyfra/litera jest taka sama, stabilność sortowania zapewni nam zachowanie pierwotnego porządku. Po ostatnim przebiegu pętli for ciągi będą uporządkowane według najbardziej znaczących cyfr, oraz kolejnych w przypadku identyczności na ostatnich pozycjach.

Powyższy algorytm zakłada, że ciągi są tej samej długości. W przypadku gdy tak nie jest, możemy uzupełnić ciągi do tej samej długości zerami z lewej strony (dla liczb) lub zerowymi znakami z prawej (dla napisów). Jeżeli ciągów długich jest niewiele, metoda ta jest nieefektywna, jednak istnieją modyfikacje oryginalnego algorytmu działające ściśle w czasie liniowym względem rozmiaru danych.

Przykład działania algorytmu sortowania pozycyjnego

^ wskazuje pozycję posortowaną w danym przejściu.

523     472     523     266
266     523     349     349
783 --> 783 --> 266 --> 472
472     266     472     523
349     349     783     783
          ^      ^      ^