Dlaczego Radix Sort ?

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 $n$$\log n$$\log n$$O(n)$$O(n \log n)$

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

jeśli mamy listę $n$ liczb, potrzebujemy $\log n$ bitów

Nie: jeśli mamy listę liczb od $0$ do $2^k - 1$ , potrzebujemy $k$ bitów. Ogólnie nie ma związku między $k$ i $\log n$ .

Jeśli wszystkie liczby są różne, wówczas $\log n \ge k$ , a sortowanie radix według różnych liczb ma złożoność czasową $\Omega(n \log n)$ . Ogólnie rzecz biorąc, złożoność sortowania w podstawach wynosi $\Theta(n \, k)$ 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.$O(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 $\Theta(n \log n)$$n!$$m$$2^m$$n!$$m \ge \log (n!) = \Theta(n \log n)$

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 $n!$$k$$n$$n \le 2^k$$\Omega(n \log n)$$n$$\Theta(n \log n)$$n \gt 2^k$

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)$$0$$k-1$$k$$\Theta(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 $d$$d$$\Theta(d(n+k))$$d$$k=O(n)$

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 = \log_2(n)$$16$