El algoritmo de ordenación Radix
1) Haga lo siguiente para cada dígito i donde i varía desde el dígito menos significativo hasta el dígito más significativo.
- Ordene la array de entrada utilizando la ordenación por conteo (o cualquier ordenación estable) de acuerdo con el i-ésimo dígito.
Python3
# Python program for implementation of Radix Sort # A function to do counting sort of arr[] according to # the digit represented by exp. def countingSort(arr, exp1): n = len(arr) # The output array elements that will have sorted arr output = [0] * (n) # initialize count array as 0 count = [0] * (10) # Store count of occurrences in count[] for i in range(0, n): index = (arr[i]/exp1) count[int((index)%10)] += 1 # Change count[i] so that count[i] now contains actual # position of this digit in output array for i in range(1,10): count[i] += count[i-1] # Build the output array i = n-1 while i>=0: index = (arr[i]/exp1) output[ count[ int((index)%10) ] - 1] = arr[i] count[int((index)%10)] -= 1 i -= 1 # Copying the output array to arr[], # so that arr now contains sorted numbers i = 0 for i in range(0,len(arr)): arr[i] = output[i] # Method to do Radix Sort def radixSort(arr): # Find the maximum number to know number of digits max1 = max(arr) # Do counting sort for every digit. Note that instead # of passing digit number, exp is passed. exp is 10^i # where i is current digit number exp = 1 while max1/exp > 0: countingSort(arr,exp) exp *= 10 # Driver code to test above arr = [ 170, 45, 75, 90, 802, 24, 2, 66] radixSort(arr) for i in range(len(arr)): print(arr[i],end=" ") # This code is contributed by Mohit Kumra # This code is updated by Sudeep Saxena(saxenasudeepcse@gmail.com) on July 9, 2020
Producción:
2 24 45 66 75 90 170 802
Consulte el artículo completo sobre Radix Sort para obtener más detalles.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA