En este tutorial, aprenderá cómo funciona la ordenación por radix. Además, encontrará ejemplos prácticos de ordenación por radix en C, C ++, Java y Python.
La ordenación por radix es una técnica de clasificación que ordena los elementos agrupando primero los dígitos individuales del mismo valor posicional . Luego, clasifique los elementos según su orden creciente / decreciente.
Supongamos que tenemos una matriz de 8 elementos. Primero, ordenaremos los elementos según el valor del lugar de la unidad. Luego, ordenaremos los elementos según el valor del décimo lugar. Este proceso continúa hasta el último lugar significativo.
Sea la matriz inicial (121, 432, 564, 23, 1, 45, 788). Está ordenado según el orden de base, como se muestra en la figura siguiente.
Trabajo de Radix Sort
Por favor, revise la clasificación de conteo antes de leer este artículo porque la clasificación de conteo se usa como una clasificación intermedia en la clasificación de base.
¿Cómo funciona Radix Sort?
- Encuentre el elemento más grande de la matriz, es decir, máx. Sea
Xel número de dígitos enmax.Xse calcula porque tenemos que pasar por todos los lugares significativos de todos los elementos.
En esta matriz(121, 432, 564, 23, 1, 45, 788), tenemos el número más grande 788. Tiene 3 dígitos. Por lo tanto, el bucle debe subir a cientos de lugares (3 veces). - Ahora, revise cada lugar significativo uno por uno.
Utilice cualquier técnica de clasificación estable para ordenar los dígitos en cada lugar significativo. Hemos utilizado el tipo de conteo para esto.
Ordene los elementos según los dígitos de la unidad de lugar (X=0).
Uso de ordenación por conteo para ordenar elementos según el lugar de la unidad - Ahora, ordena los elementos según los dígitos en el lugar de las decenas.
Ordenar elementos según el lugar de las decenas - Finalmente, ordena los elementos según los dígitos en centenas.
Ordenar elementos basados en cientos de lugares
Algoritmo de clasificación por radix
radixSort (matriz) d <- número máximo de dígitos en el elemento más grande crear d cubos de tamaño 0-9 para i <- 0 ad ordene los elementos de acuerdo con los dígitos del i-ésimo lugar usando countingSort counttingSort (matriz, d) max <- encontrar el elemento más grande entre los elementos del lugar dth inicializa la matriz de recuento con todos los ceros para j <- 0 para medir el tamaño encuentre el recuento total de cada dígito único en el lugar dth de los elementos y almacene el recuento en el índice jth en la matriz de recuento para i <- 1 a la búsqueda máxima la suma acumulativa y almacenarla en la matriz de recuento para j <- reducir el tamaño a 1 restaurar los elementos a la matriz reducir el recuento de cada elemento restaurado en 1
Ejemplos de Python, Java y 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); )
Complejidad
Dado que el ordenamiento por radix es un algoritmo no comparativo, tiene ventajas sobre los algoritmos de ordenamiento comparativo.
Para el tipo de base que usa el tipo de conteo como un tipo estable intermedio, la complejidad de tiempo es O(d(n+k)).
Aquí, destá el ciclo numérico y O(n+k)es la complejidad del tiempo del tipo de conteo.
Por lo tanto, la ordenación por radix tiene una complejidad de tiempo lineal que es mejor que la O(nlog n)de los algoritmos de ordenación comparativa.
Si tomamos números de dígitos muy grandes o el número de otras bases como números de 32 y 64 bits, entonces puede funcionar en tiempo lineal, sin embargo, la clasificación intermedia ocupa un gran espacio.
Esto hace que el espacio de clasificación de radix sea ineficaz. Esta es la razón por la que este tipo no se usa en bibliotecas de software.
Aplicaciones de clasificación por radix
La ordenación por radix se implementa en
- Algoritmo DC3 (Kärkkäinen-Sanders-Burkhardt) mientras crea una matriz de sufijos.
- lugares donde hay números en grandes rangos.
