Dlaczego Radix Sort ?

23

W sortowaniu radix najpierw sortujemy według najmniej znaczącej cyfry, a następnie sortujemy według drugiej najmniej znaczącej cyfry itd. I kończymy na posortowanej liście.

Teraz, jeśli mamy listę liczb, potrzebujemy bitów, aby odróżnić te liczby. Tak więc liczba wykonanych przez nas przejść sortowania będzie wynosić . Każde przejście zajmuje czas O (n), a zatem czas działania sortowania radix wynosi O (n \ log n)log n log n O ( n )nlognlognO(n)O(nlogn)

Ale dobrze wiadomo, że jest to liniowy algorytm czasu. Dlaczego?

Pratik Deoghare
źródło
Dlatego liniowe sortowanie czasowe zwykle wymaga, aby dane wejściowe były liczbami całkowitymi w pewnym ustalonym zakresie. Sortowanie Radix wymaga stałego zakresu cyfr. W twoim przykładzie zakładałeś, że zakres wynosił [0,1] , ale dla cyfr możliwy jest dowolny zakres liczb całkowitych; na przykład mógłbyś wybrać [0,n]
Joe,

Odpowiedzi:

19

jeśli mamy listę n liczb, potrzebujemy logn bitów

Nie: jeśli mamy listę liczb od 0 do 2k1 , potrzebujemy k bitów. Ogólnie nie ma związku między k i logn .

Jeśli wszystkie liczby są różne, wówczas lognk , a sortowanie radix według różnych liczb ma złożoność czasową Ω(nlogn) . Ogólnie rzecz biorąc, złożoność sortowania w podstawach wynosi Θ(nk) gdzie n to liczba elementów do posortowania, a k to liczba bitów w każdym elemencie.

Stwierdzenie, że złożoność sortowania w radix wynosi oznacza przyjęcie stałego rozmiaru bitu dla liczb. Oznacza to, że dla wystarczająco dużej liczby będzie wiele zduplikowanych wartości.nO(n)n


Istnieje ogólne twierdzenie, że metoda sortowania tablic lub list, która działa poprzez porównywanie dwóch elementów jednocześnie, nie może działać szybciej niż w najgorszym przypadku. Sortowanie Radix nie działa przez porównywanie elementów, ale działa ta sama metoda sprawdzania. Sortowanie Radix jest procesem decyzyjnym określającym, która permutacja ma zostać zastosowana do tablicy; jestpermutacje tablicy i sortowanie radix podejmuje decyzje binarne, tzn. decyduje, czy zamienić dwa elementy na każdym etapie. Po decyzji binarnych, sortowanie pozycyjne może zdecydować między permutacji. Aby dotrzeć domożliwe permutacje, konieczne jest, aby .n ! m 2 m n ! m log ( n ! ) = Θ ( n log n )Θ(nlogn)n!m2mn!mlog(n!)=Θ(nlogn)

Założeniem w dowodzie, że nie napisałem powyżej, jest to, że algorytm musi działać w przypadku, gdy elementy są różne. Jeśli wiadomo z góry, że wszystkie elementy nie są różne, to liczba potencjalnych permutacji jest mniejsza niż pełne. Podczas sortowania liczb bitowych możliwe jest posiadanie różnych elementów, gdy ; w takim przypadku złożoność sortowania radix jest rzeczywiście . W przypadku większych wartości muszą wystąpić kolizje, co wyjaśnia, w jaki sposób sortowanie radix może mieć złożoność mniejszą niż gdy .k n n 2 k Ω ( n log n ) n Θ ( n log n ) n > 2 kn!knn2kΩ(nlogn)nΘ(nlogn)n>2k

Gilles „SO- przestań być zły”
źródło
1
Alternatywnym punktem widzenia jest model kosztów słowo-RAM: Nasza maszyna może pracować z liczbami całkowitymi bitów w stałym czasie. (Bieżące maszyny mają ). W ten sposób jeden krok sortowania z wiaderkami można wykonać w czasie , bezpośrednio uzyskując dostęp do odpowiedniego elementu tablicy. W ten sposób sortowanie radix jest liniowe dla liczb całkowitych każdy. w = 64 2 w O ( 1 ) n w = O ( log n )ww=642)wO(1)nw=O(logn)
Sebastian
9

Uważaj na swoją analizę: co zakładasz, aby sortowanie przebiegało w czasie ? Wynika to z tego, że każda z twoich cyfr mieści się w zakresie od do , co oznacza, że ​​twoje cyfry mogą przyjmować możliwych wartości. Potrzebujesz stabilnego algorytmu sortowania, więc możesz na przykład wybrać sortowanie według liczenia. Zliczanie sortowania przebiega w czasie . Jeśli , sortowanie zliczające przebiega w czasie liniowym.0 k - 1 k Θ ( n + k ) k = O ( n )O(n)0k-1kΘ(n+k)k=O(n)

Każdy z ciągów znaków lub cyfr ma cyfry . Jak mówisz, wykonujesz nad nimi . Stąd sortowanie radix wyraźnie działa w czasie . Ale jeśli uważamy, że jest stałe, a , widzimy, że sortowanie radix przebiega w czasie liniowym.d Θ ( d ( n + k ) ) d k = O ( n )rereΘ(d(n+k))dk=O(n)

Juho
źródło
1
Załóżmy na przykład, że sortujesz liczby całkowite z zakresu dla niektórych dla stałej . Wtedy możesz mieć cyfry każda z zakresem . [0,N1]N=O(nd)dO(d)O(n)
Joe
-2

Myślę, że założenie jest błędne. Możesz wykonać sortowanie za pomocą liczb w liczbach np. Szesnastkowych. Zatem na każdym kroku dzielisz tablicę liczb na segmentów.k=log2(n)16

Alexandre Kandalintsev
źródło
6
Jeśli chodzi o big-O, nie ma różnicy między a . log2nlog16n
Rick Decker,