W tym samouczku dowiesz się, jak działa sortowanie radix. Znajdziesz również działające przykłady sortowania radix w językach C, C ++, Java i Python.
Sortowanie radix to technika sortowania, która sortuje elementy, najpierw grupując poszczególne cyfry tej samej wartości miejsca . Następnie posortuj elementy zgodnie z ich kolejnością rosnącą / malejącą.
Załóżmy, że mamy tablicę 8 elementów. Najpierw posortujemy elementy na podstawie wartości miejsca jednostkowego. Następnie posortujemy elementy według wartości dziesiątego miejsca. Ten proces trwa do ostatniego znaczącego miejsca.
Niech początkowa tablica będzie (121, 432, 564, 23, 1, 45, 788). Jest sortowany według sortowania radix, jak pokazano na poniższym rysunku.
Działanie Radix Sort
Przed przeczytaniem tego artykułu należy przejść przez sortowanie według liczenia, ponieważ sortowanie według liczenia jest używane jako sortowanie pośrednie w sortowaniu radix.
Jak działa sortowanie Radix?
- Znajdź największy element w tablicy, tj. Max. Niech
Xbędzie liczbą cyfrmax.Xjest obliczana, ponieważ musimy przejść przez wszystkie znaczące miejsca wszystkich elementów.
W tej tablicy(121, 432, 564, 23, 1, 45, 788)mamy największą liczbę 788. Ma 3 cyfry. Dlatego pętla powinna dojść do setek miejsc (3 razy). - Teraz przejdź przez każde znaczące miejsce po kolei.
Użyj dowolnej stabilnej techniki sortowania, aby posortować cyfry w każdym znaczącym miejscu. Użyliśmy do tego sortowania liczącego.
Sortuj elementy w oparciu o cyfry miejsca jednostki (X=0).
Używanie sortowania liczącego do sortowania elementów na podstawie miejsca jednostkowego - Teraz posortuj elementy według cyfr w dziesiątkach.
Sortuj elementy według miejsca dziesiątek - Na koniec posortuj elementy na podstawie cyfr w setkach miejsc.
Sortuj elementy według setek miejsc
Algorytm sortowania radix
radixSort (tablica) d <- maksymalna liczba cyfr w największym elemencie stwórz d koszy o rozmiarze 0-9 dla i <- 0 do d sortuj elementy według i-tego miejsca przy pomocy countingSort countingSort (array, d) max <- find największy element wśród elementów d-tego miejsca inicjalizuj tablicę count ze wszystkimi zerami dla j <- 0, aby określić rozmiar, znajdź całkowitą liczbę każdej unikalnej cyfry na d-tym miejscu elementów i zapisz licznik w j-tym indeksie w tablicy count dla i <- 1 do max znajdź skumulowaną sumę i zapisz ją w tablicy count dla j <- rozmiar do 1 przywróć elementy do tablicy zmniejsz liczbę każdego przywracanego elementu o 1
Przykłady w Pythonie, Javie i C / C ++
Python Java C C ++ # Radix sort in Python # Using counting sort to sort the elements in the basis of significant places def countingSort(array, place): size = len(array) output = (0) * size count = (0) * 10 # Calculate count of elements for i in range(0, size): index = array(i) // place count(index % 10) += 1 # Calculate cummulative count for i in range(1, 10): count(i) += count(i - 1) # Place the elements in sorted order i = size - 1 while i>= 0: index = array(i) // place output(count(index % 10) - 1) = array(i) count(index % 10) -= 1 i -= 1 for i in range(0, size): array(i) = output(i) # Main function to implement radix sort def radixSort(array): # Get maximum element max_element = max(array) # Apply counting sort to sort elements based on place value. place = 1 while max_element // place> 0: countingSort(array, place) place *= 10 data = (121, 432, 564, 23, 1, 45, 788) radixSort(data) print(data)
// Radix Sort in Java Programming import java.util.Arrays; class RadixSort ( // Using counting sort to sort the elements in the basis of significant places void countingSort(int array(), int size, int place) ( int() output = new int(size + 1); int max = array(0); for (int i = 1; i max) max = array(i); ) int() count = new int(max + 1); for (int i = 0; i < max; ++i) count(i) = 0; // Calculate count of elements for (int i = 0; i < size; i++) count((array(i) / place) % 10)++; // Calculate cummulative count for (int i = 1; i <10; i++) count(i) += count(i - 1); // Place the elements in sorted order for (int i = size - 1; i>= 0; i--) ( output(count((array(i) / place) % 10) - 1) = array(i); count((array(i) / place) % 10)--; ) for (int i = 0; i < size; i++) array(i) = output(i); ) // Function to get the largest element from an array int getMax(int array(), int n) ( int max = array(0); for (int i = 1; i max) max = array(i); return max; ) // Main function to implement radix sort void radixSort(int array(), int size) ( // Get maximum element int max = getMax(array, size); // Apply counting sort to sort elements based on place value. for (int place = 1; max / place> 0; place *= 10) countingSort(array, size, place); ) // Driver code public static void main(String args()) ( int() data = ( 121, 432, 564, 23, 1, 45, 788 ); int size = data.length; RadixSort rs = new RadixSort(); rs.radixSort(data, size); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )
// Radix Sort in C Programming #include // Function to get the largest element from an array int getMax(int array(), int n) ( int max = array(0); for (int i = 1; i max) max = array(i); return max; ) // Using counting sort to sort the elements in the basis of significant places void countingSort(int array(), int size, int place) ( int output(size + 1); int max = (array(0) / place) % 10; for (int i = 1; i max) max = array(i); ) int count(max + 1); for (int i = 0; i < max; ++i) count(i) = 0; // Calculate count of elements for (int i = 0; i < size; i++) count((array(i) / place) % 10)++; // Calculate cummulative count for (int i = 1; i <10; i++) count(i) += count(i - 1); // Place the elements in sorted order for (int i = size - 1; i>= 0; i--) ( output(count((array(i) / place) % 10) - 1) = array(i); count((array(i) / place) % 10)--; ) for (int i = 0; i 0; place *= 10) countingSort(array, size, place); ) // Print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // Driver code int main() ( int array() = (121, 432, 564, 23, 1, 45, 788); int n = sizeof(array) / sizeof(array(0)); radixsort(array, n); printArray(array, n); )
// Radix Sort in C++ Programming #include using namespace std; // Function to get the largest element from an array int getMax(int array(), int n) ( int max = array(0); for (int i = 1; i max) max = array(i); return max; ) // Using counting sort to sort the elements in the basis of significant places void countingSort(int array(), int size, int place) ( const int max = 10; int output(size); int count(max); for (int i = 0; i < max; ++i) count(i) = 0; // Calculate count of elements for (int i = 0; i < size; i++) count((array(i) / place) % 10)++; // Calculate cummulative count for (int i = 1; i = 0; i--) ( output(count((array(i) / place) % 10) - 1) = array(i); count((array(i) / place) % 10)--; ) for (int i = 0; i 0; place *= 10) countingSort(array, size, place); ) // Print an array void printArray(int array(), int size) ( int i; for (i = 0; i < size; i++) cout << array(i) << " "; cout << endl; ) // Driver code int main() ( int array() = (121, 432, 564, 23, 1, 45, 788); int n = sizeof(array) / sizeof(array(0)); radixsort(array, n); printArray(array, n); )
Złożoność
Ponieważ sortowanie radix jest algorytmem nieporównawczym, ma przewagę nad algorytmami sortowania porównawczego.
W przypadku sortowania radix, które wykorzystuje sortowanie zliczające jako pośrednie sortowanie stabilne, złożoność czasowa wynosi O(d(n+k)).
Tutaj djest cykl liczbowy i O(n+k)złożoność czasowa sortowania zliczania.
Zatem sortowanie radix ma liniową złożoność czasową, która jest lepsza niż O(nlog n)algorytmy sortowania porównawczego.
Jeśli weźmiemy bardzo duże liczby cyfrowe lub liczbę innych zasad, takich jak liczby 32-bitowe i 64-bitowe, to może on działać w czasie liniowym, jednak sortowanie pośrednie zajmuje dużo miejsca.
To sprawia, że przestrzeń sortowania radix jest nieefektywna. To jest powód, dla którego ten rodzaj nie jest używany w bibliotekach oprogramowania.
Aplikacje Radix Sort
Sortowanie radix jest zaimplementowane w
- Algorytm DC3 (Kärkkäinen-Sanders-Burkhardt) podczas tworzenia tablicy sufiksów.
- miejsca, w których występują liczby w dużych zakresach.
