Loading AI tools
Z Wikipedii, wolnej encyklopedii
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[1]. Złożoność obliczeniowa jest równa gdzie to liczba różnych cyfr, a liczba cyfr w kluczach[1]. Wymaga dodatkowej pamięci.
Przewagą sortowania pozycyjnego nad innymi metodami jest fakt, iż nie wykonuje ono żadnych operacji porównania na danych wejściowych[1]. 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[1]. Gdybyśmy do posortowania tych liczb zastosowali algorytm porównujący liczby, np. sortowanie szybkie, otrzymalibyśmy dla niego złożoność gdzie to liczba cyfr w liczbach[2].
Dla krótkich ciągów efektywniejsze jest sortowanie przez zliczanie[1].
Algorytmy pozycyjne sprawdzają się także w roli algorytmów sortujących listy.
tab[]
– tablica ciągów (cyfr, liter itp.) gdzie pozycja 1 oznacza najbardziej znaczącą pozycje ciągud
– długość ciągówprocedure RadixSort(tab[],d)
begin
for i:=d downto 1 do
posortuj stabilnie ciągi według i-tej pozycji;
end;
Ta sekcja od 2011-04 wymaga zweryfikowania podanych informacji. |
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.
^
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 ^ ^ ^
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.