Sortowanie pozycyjne
Z Wikipedii
 |
Ten artykuł wymaga dopracowania zgodnie z zaleceniami edycyjnymi. Należy w nim poprawić: styl (zdania rozpoczynajace się od ,,a więc", ,,wyobraź sobie", wykrzykniki...). Po naprawieniu wszystkich błędów można usunąć tę wiadomość. |
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 wielkość domeny cyfr, a d szerokość kluczy w cyfrach. Wymaga O(n + k) dodatkowej pamięci.
Przewagą sortowania pozycyjnego nad innymi metodami jest fakt, iż nie wykonuje on żadnych operacji na danych wejściowych - wyobraź sobie, że mamy dużą liczbę bardzo długich liczb, bardzo do siebie podobnych - w tym sensie, że prawdopodobieństwo tego, że większość z nich ma takie same cyfry na poszczególnych pozycjach jest duże. W szczególności dotyczy to cyfr wiodących - nie jest łatwo powiedzieć która jest większa, gdyż za każdym razem musimy schodzić głęboko "w głąb" liczb. A więc czas porównania takich liczb jest bardzo duży. Gdybyśmy do posortowania tych liczb zastosowali inny algorytm, np. Quicksort, otrzymalibyśmy dla nich złożoność O(nlogn) = C * nlogn gdzie C jest czasem między innymi porównania dwóch liczb - w przypadku naszych "złośliwych danych" stała ta mogłaby być znacznie większa od nlogn, gdzie n to ilość liczb (a nie ich długość!). A więc asymptotycznie lepszy Quicksort w praktyce mógłby okazać się gorszy od RadixSort'a, który porównuje tylko pojedyncze cyfry!
Algorytmy pozycyjne bardzo dobrze sprawdzają się także w roli algorytmów sortujących listy. Przykładem bardzo efektywnej i praktycznej implementacji algorytmu pozycyjnego sortującego listy jest Pbit. Pierwszy algorytm pozycyjny sortujący listy został zaprezentowany przez Steven Pigeon w Dr. Dobb's Journal, May 2002, pp. 89-94.
[edytuj] Implementacja w pseudojęzyku programowania
- tab[] - tablica ciagów (cyfr,liter itp) gdzie pozycja 1 oznacza najbardziej znaczącą pozycje ciągu
- n - długość ciągów
procedure RadixSort(tab[],n)
begin
for i:=n downto 1 do
posortuj stabilnie ciągi według i-tej pozycji;
end;
[edytuj] 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.
UWAGA!!! Powyższy algorytm zakłada, że ciągi są tej samej długości - w przypadku gdy tak nie jest, możemy uzupełnić "za krótkie" ciągi zerami lub znakami pustymi.
[edytuj] Przykład działania algorytmu sortowania pozycyjnego
^ oznacza aktualnÄ… pozycjÄ™. 523 472 523 266 266 523 349 349 783 --> 783 --> 266 --> 472 472 266 472 523 349 349 783 783 ^ ^ ^ ^
| 4000 GB w zsypie |
|
Serwer, z którego nielegalnie można było pobrać 4000 gigabajtów nielegalnych gier, filmów, muzyki i programów zabezpieczyli policjanci z KWP. Administratorowi i właścicielowi serwera grozi do pięciu lat więzienia.
|
| Społecznościowy antywirus? |
|
Czy możliwe jest wykorzystanie potencjału społeczności internetowych, lub użytkowników sieci do ochrony komputera przed zagrożeniami płynącymi z sieci? Producent oprogramowania antywirusowego, Panda Security, właśnie takie rozwiązania planuje wprowadzić w swoich najnowszych produktach.
|
| Mozilla aktualizuje Thunderbird'a |
|
W ostatnią środę Mozilla udostępniła na swoich serwerach najnowszą wersję programu pocztowego Thunderbird 2.0.0.16, wzbogaconą o dziewięć zasadniczych poprawek.
|
| Internetowy tablet z Firefoksem |
|
Michael Arrington planuje stworzyć stylowy tablet, który służyć ma wyłącznie do surfowania w internecie.
|
| Wielofunkcyjna stacja dokujÄ…ca |
|
Stacje dokujące i huby USB to urządzenia przygotowane z myślą o osobach, którym ciągle brakuje gniazd przyłączeniowych.
|