DAA - sortowanie radix

Radix sortto mała metoda, której wiele osób używa intuicyjnie podczas alfabetyzacji dużej listy nazwisk. W szczególności lista nazwisk jest najpierw sortowana według pierwszej litery każdego nazwiska, to znaczy nazwiska są uporządkowane w 26 klasach.

Intuicyjnie można posortować liczby według ich najbardziej znaczącej cyfry. Jednak sortowanie Radix działa wbrew intuicji, sortując najpierw najmniej znaczące cyfry. W pierwszym przebiegu wszystkie liczby są sortowane według najmniej znaczącej cyfry i łączone w tablicę. Następnie w drugim przebiegu całe liczby są ponownie sortowane według drugich najmniej znaczących cyfr i łączone w tablicę i tak dalej.

Algorithm: Radix-Sort (list, n) 
shift = 1 
for loop = 1 to keysize do 
   for entry = 1 to n do 
      bucketnumber = (list[entry].key / shift) mod 10 
      append (bucket[bucketnumber], list[entry]) 
   list = combinebuckets() 
   shift = shift * 10

Analiza

Każdy klawisz jest sprawdzany od razu pod kątem każdej cyfry (lub litery, jeśli klawisze są alfabetyczne) najdłuższego klucza. Stąd, jeśli najdłuższy klucz mam cyfry i są n klucze, sortowanie radix ma porządek O(m.n).

Jeśli jednak spojrzymy na te dwie wartości, rozmiar kluczy będzie stosunkowo mały w porównaniu z liczbą kluczy. Na przykład, jeśli mamy sześciocyfrowe klucze, moglibyśmy mieć milion różnych rekordów.

Tutaj widzimy, że rozmiar kluczy nie jest znaczący, a ten algorytm ma liniową złożoność O(n).

Przykład

Poniższy przykład pokazuje, jak sortowanie Radix działa na siedmiu 3-cyfrowych liczbach.

Wejście	1 st Przełęcz	2 ND Przełęcz	3 rd Pass
329	720	720	329
457	355	329	355
657	436	436	436
839	457	839	457
436	657	355	657
720	329	457	720
355	839	657	839

W powyższym przykładzie pierwsza kolumna to dane wejściowe. Pozostałe kolumny pokazują listę po kolejnych sortowaniach na coraz bardziej znaczących pozycjach cyfr. Kod sortowania Radix zakłada, że ​​każdy element w tablicyA z n elementy ma d cyfry, gdzie cyfra 1 to cyfra najniższego rzędu i d to cyfra najwyższego rzędu.