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 on ż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(dnlogn) gdzie d to liczba cyfr w liczbach.
Algorytmy pozycyjne sprawdzają się także w roli algorytmów sortujących
listy
.
Implementacja w pseudojęzyku programowania
- tab[] – tablica ciagó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 dobrego 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
^ oznacza aktualną pozycję.523 472 523 266266 523 349 349783 --> 783 --> 266 --> 472472 266 472 523349 349 783 783 ^ ^ ^ ^