Sortowanie pozycyjne

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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(d n \log n) 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[edytuj | edytuj kod]

  • 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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

^ 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
          ^      ^      ^