Radix Suerte es un algoritmo de clasificación lineal que clasifica elementos procesándolos dígito por dígito. Es un algoritmo de clasificación eficiente para números enteros o cadenas con claves de tamaño fijo.
En lugar de comparar elementos directamente, Radix Sort distribuye los elementos en grupos según el valor de cada dígito. Al ordenar repetidamente los elementos por sus dígitos significativos, desde el menos significativo hasta el más significativo, Radix Sort logra el orden final.
Algoritmo de clasificación de Radix
La idea clave detrás de Radix Sort es explotar el concepto de valor posicional. Se supone que ordenar números dígito por dígito eventualmente dará como resultado una lista completamente ordenada. La clasificación por base se puede realizar utilizando diferentes variaciones, como la clasificación por base del dígito menos significativo (LSD) o la clasificación por base del dígito más significativo (MSD).
¿Cómo funciona el algoritmo de clasificación Radix?
Para realizar la clasificación por base en la matriz [170, 45, 75, 90, 802, 24, 2, 66], seguimos estos pasos:
¿Cómo funciona el algoritmo de clasificación Radix? Paso 1
Paso 1: Encuentre el elemento más grande en la matriz, que es 802. Tiene tres dígitos, por lo que iteraremos tres veces, una por cada lugar significativo.
Paso 2: Ordena los elementos según los dígitos del lugar de la unidad (X=0). Utilizamos una técnica de clasificación estable, como la clasificación por conteo, para ordenar los dígitos en cada lugar significativo.
programa en javaClasificación según el lugar de la unidad:
- Realice una clasificación de conteo en la matriz según los dígitos del lugar de la unidad.
- La matriz ordenada según el lugar de la unidad es [170, 90, 802, 2, 24, 45, 75, 66].
¿Cómo funciona el algoritmo de clasificación Radix? Paso 2
Paso 3: Ordena los elementos según los dígitos del lugar de las decenas.
booleano a cadenaClasificación según el lugar de las decenas:
- Realice una clasificación de conteo en la matriz según los dígitos del lugar de las decenas.
- La matriz ordenada según el lugar de las decenas es [802, 2, 24, 45, 66, 170, 75, 90].
¿Cómo funciona el algoritmo de clasificación Radix? Paso 3
Etapa 4: Ordena los elementos según los dígitos del lugar de las centenas.
Clasificación basada en el lugar de las centenas:
- Realice una clasificación de conteo en la matriz según los dígitos de las centenas.
- La matriz ordenada según las centenas es [2, 24, 45, 66, 75, 90, 170, 802].
¿Cómo funciona el algoritmo de clasificación Radix? Etapa 4
Paso 5: La matriz ahora está ordenada en orden ascendente.
La matriz ordenada final usando clasificación por base es [2, 24, 45, 66, 75, 90, 170, 802].
¿Cómo funciona el algoritmo de clasificación Radix? Paso 5
A continuación se muestra la implementación de las ilustraciones anteriores:
C++ // C++ implementation of Radix Sort #include using namespace std; // A utility function to get maximum // value in arr[] int getMax(int arr[], int n) { int mx = arr[0]; for (int i = 1; i < n; i++) if (arr[i]>mx) mx = arreglo[i]; devolver mx; } // Una función para contar tipo arr[] // según el dígito // representado por exp. void countSort(int arr[], int n, int exp) { // Matriz de salida int salida[n]; int i, cuenta[10] = { 0 }; // Almacenar el recuento de ocurrencias // en el recuento[] for (i = 0; i< n; i++) count[(arr[i] / exp) % 10]++; // Change count[i] so that count[i] // now contains actual position // of this digit in output[] for (i = 1; i < 10; i++) count[i] += count[i - 1]; // Build the output array for (i = n - 1; i>= 0; i--) { salida[cuenta[(arreglo[i] / exp) % 10] - 1] = arreglo[i]; contar[(arr[i] / exp) % 10]--; } // Copiar la matriz de salida a arr[], // para que arr[] ahora contenga // números ordenados según el dígito actual para (i = 0; i< n; i++) arr[i] = output[i]; } // The main function to that sorts arr[] // of size n using Radix Sort void radixsort(int arr[], int n) { // Find the maximum number to // know number of digits int m = getMax(arr, n); // 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 for (int exp = 1; m / exp>0; exp *= 10) countSort(arr, n, exp); } // Una función de utilidad para imprimir una matriz void print(int arr[], int n) { for (int i = 0; i< n; i++) cout << arr[i] << ' '; } // Driver Code int main() { int arr[] = { 170, 45, 75, 90, 802, 24, 2, 66 }; int n = sizeof(arr) / sizeof(arr[0]); // Function Call radixsort(arr, n); print(arr, n); return 0; }> Java // Radix sort Java implementation import java.io.*; import java.util.*; class Radix { // A utility function to get maximum value in arr[] static int getMax(int arr[], int n) { int mx = arr[0]; for (int i = 1; i < n; i++) if (arr[i]>mx) mx = arreglo[i]; devolver mx; } // Una función para contar tipo arr[] según // el dígito representado por exp. static void countSort(int arr[], int n, int exp) { int salida[] = new int[n]; // matriz de salida int i; int recuento[] = nuevo int[10]; Arrays.fill(recuento, 0); // Almacena el recuento de ocurrencias en count[] for (i = 0; i< n; i++) count[(arr[i] / exp) % 10]++; // Change count[i] so that count[i] now contains // actual position of this digit in output[] for (i = 1; i < 10; i++) count[i] += count[i - 1]; // Build the output array for (i = n - 1; i>= 0; i--) { salida[cuenta[(arreglo[i] / exp) % 10] - 1] = arreglo[i]; contar[(arr[i] / exp) % 10]--; } // Copiar la matriz de salida a arr[], de modo que arr[] ahora // contenga números ordenados según el // dígito actual para (i = 0; i< n; i++) arr[i] = output[i]; } // The main function to that sorts arr[] of // size n using Radix Sort static void radixsort(int arr[], int n) { // Find the maximum number to know number of digits int m = getMax(arr, n); // 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 for (int exp = 1; m / exp>0; exp *= 10) countSort(arr, n, exp); } // Una función de utilidad para imprimir una matriz estática void print(int arr[], int n) { for (int i = 0; i< n; i++) System.out.print(arr[i] + ' '); } // Main driver method public static void main(String[] args) { int arr[] = { 170, 45, 75, 90, 802, 24, 2, 66 }; int n = arr.length; // Function Call radixsort(arr, n); print(arr, n); } }> 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[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 salida[count[index % 10] - 1] = arr[i] count[index % 10] -= 1 i -= 1 # Copiando la matriz de salida a arr[] , # de modo que arr ahora contenga números ordenados i = 0 para i en range(0, len(arr)): arr[i] = salida[i] # Método para hacer Radix Sort def radixSort(arr): # Encuentra el máximo número para saber el número de dígitos max1 = max(arr) # Ordene contando para cada dígito. Tenga en cuenta que en lugar de # pasar el número de dígito, se pasa exp. exp es 10^i # donde i es el dígito actual exp = 1 mientras max1 / exp>= 1: countingSort(arr, exp) exp *= 10 # Código del controlador arr = [170, 45, 75, 90, 802, 24 , 2, 66] # Llamada a función radixSort(arr) para i in range(len(arr)): print(arr[i], end=' ') # Este código es una contribución de Mohit Kumra # Editado por Patrick Gallagher>
C# // C# implementation of Radix Sort using System; class GFG { public static int getMax(int[] arr, int n) { int mx = arr[0]; for (int i = 1; i < n; i++) if (arr[i]>mx) mx = arreglo[i]; devolver mx; } // Una función para contar tipo arr[] según // el dígito representado por exp. public static void countSort(int[] arr, int n, int exp) { int[] salida = new int[n]; // matriz de salida int i; int[] recuento = nuevo int[10]; // inicializando todos los elementos del recuento a 0 for (i = 0; i< 10; i++) count[i] = 0; // Store count of occurrences in count[] for (i = 0; i < n; i++) count[(arr[i] / exp) % 10]++; // Change count[i] so that count[i] now contains // actual // position of this digit in output[] for (i = 1; i < 10; i++) count[i] += count[i - 1]; // Build the output array for (i = n - 1; i>= 0; i--) { salida[cuenta[(arreglo[i] / exp) % 10] - 1] = arreglo[i]; contar[(arr[i] / exp) % 10]--; } // Copiar la matriz de salida a arr[], de modo que arr[] ahora // contenga números ordenados según el // dígito actual para (i = 0; i< n; i++) arr[i] = output[i]; } // The main function to that sorts arr[] of size n using // Radix Sort public static void radixsort(int[] arr, int n) { // Find the maximum number to know number of digits int m = getMax(arr, n); // 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 for (int exp = 1; m / exp>0; exp *= 10) countSort(arr, n, exp); } // Una función de utilidad para imprimir una matriz public static void print(int[] arr, int n) { for (int i = 0; i< n; i++) Console.Write(arr[i] + ' '); } // Driver Code public static void Main() { int[] arr = { 170, 45, 75, 90, 802, 24, 2, 66 }; int n = arr.Length; // Function Call radixsort(arr, n); print(arr, n); } // This code is contributed by DrRoot_ }> JavaScript // Radix sort JavaScript implementation 'use strict'; // A utility function to get maximum value in arr[] function getMax(arr) { const length = arr.length; let mx = arr[0]; for (let i = 1; i < length; i++) { if (arr[i]>mx) mx = arreglo[i]; } devolver mx; } // Una función para contar tipo arr[] según // el dígito representado por exp. función countSort(arr, exp) { longitud constante = longitud.arr; let salida = Matriz(longitud); // matriz de salida let count = Array(10).fill(0, 0); // Almacena el recuento de ocurrencias en count[] for (let i = 0; i< length; i++) { const digit = Math.floor(arr[i] / exp) % 10; count[digit]++; } // Change count[i] so that count[i] now contains // actual position of this digit in output[] for (let i = 1; i < 10; i++) { count[i] += count[i - 1]; } // Build the output array for (let i = length - 1; i>= 0; i--) { dígito constante = Math.floor(arr[i] / exp) % 10; salida[recuento[dígito] - 1] = arreglo[i]; contar[dígito]--; } devolver salida; } // La función principal que ordena arr[] usando Radix Sort function radixSort(arr) { // Encuentra el número máximo para saber el número de dígitos const maxNumber = getMax(arr); // Crea una copia superficial donde se guardarán los valores ordenados let sortedArr = [...arr]; // Ordena el conteo para cada dígito. Tenga en cuenta que // en lugar de pasar el número de dígito, se pasa exp. // exp es 10^i donde i es el número de dígito actual for (let exp = 1; Math.floor(maxNumber / exp)> 0; exp *= 10) { // Obtener la iteración de clasificación de recuento const sortedIteration = countSort(sortedArr , Exp); sortedArr = sortedIteration; } devolver Arr ordenado; } /*Código de controlador*/ const arr = [170, 45, 75, 90, 802, 24, 2, 66]; // Llamada a función const sortedArr = radixSort(arr); console.log(sortedArr.join(' ')); // Este código es aportado por beeduhboodee> PHP // PHP implementation of Radix Sort // A function to do counting sort of arr[] // according to the digit represented by exp. function countSort(&$arr, $n, $exp) { $output = array_fill(0, $n, 0); // output array $count = array_fill(0, 10, 0); // Store count of occurrences in count[] for ($i = 0; $i < $n; $i++) $count[ ($arr[$i] / $exp) % 10 ]++; // Change count[i] so that count[i] // now contains actual position of // this digit in output[] for ($i = 1; $i < 10; $i++) $count[$i] += $count[$i - 1]; // Build the output array for ($i = $n - 1; $i>= 0; $i--) { $salida[$cuenta[ ($arr[$i] / $exp) % 10 ] - 1] = $arr[$i]; $cuenta[ ($arr[$i] / $exp) % 10 ]--; } // Copiar la matriz de salida a arr[], de manera que // ese arr[] ahora contenga números ordenados // según el dígito actual para ($i = 0; $i< $n; $i++) $arr[$i] = $output[$i]; } // The main function to that sorts arr[] // of size n using Radix Sort function radixsort(&$arr, $n) { // Find the maximum number to know // number of digits $m = 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 for ($exp = 1; $m / $exp>0; $exp *= 10) countSort($arr, $n, $exp); } // Una función de utilidad para imprimir una función de matriz PrintArray(&$arr,$n) { for ($i = 0; $i< $n; $i++) echo $arr[$i] . ' '; } // Driver Code $arr = array(170, 45, 75, 90, 802, 24, 2, 66); $n = count($arr); // Function Call radixsort($arr, $n); PrintArray($arr, $n); // This code is contributed by rathbhupendra ?>> Dardo // Radix sort Dart implementation /// A utility function to get the maximum value of a `List` [array] int getMax(List matriz) { int max = matriz[0]; for (final it en matriz) { if (it> max) { max = it; } } retorno máximo; } /// Una función para contar el tipo `List` [matriz] de acuerdo con el /// dígito representado por [exp]. Lista contarOrdenar(Lista matriz, int exp) { longitud final = matriz.longitud; salida finalArr = List.filled(longitud, 0); // Una lista donde el índice representa el dígito y el valor representa el recuento de // apariciones final digitsCount = List.filled(10, 0); // Almacena el recuento de ocurrencias en digitsCount[] for (elemento final en la matriz) { dígito final = elemento ~/ exp % 10; dígitosCount[dígito]++; } // Cambie dígitosCount[i] para que dígitosCount[i] ahora contenga la posición real // de este dígito en OutputArr[] for (int i = 1; i< 10; i++) { digitsCount[i] += digitsCount[i - 1]; } // Build the output array for (int i = length - 1; i>= 0; i--) { elemento final = matriz[i]; dígito final = artículo ~/ exp % 10; OutputArr[dígitosCount[dígito] - 1] = elemento; dígitosCount[dígito]--; } devolver salidaArr; } /// La función principal que ordena una `Lista` [matriz] usando Radix sort List ordenar por raíz (lista array) { // Encuentra el número máximo para saber el número de dígitos final maxNumber = getMax(array); // Copia superficial de la matriz de entrada final sortedArr = List.of(array); // Ordena el conteo para cada dígito. Tenga en cuenta que en lugar de pasar dígito // número, se pasa exp. exp es 10^i, donde i es el número de dígito actual para (int exp = 1; maxNumber ~/ exp> 0; exp *= 10) { final sortedIteration = countSort(sortedArr, exp); ordenadoArr.clear(); ordenadoArr.addAll(ordenadoIteración); } devolver Arr ordenado; } void main() { matriz constante = [170, 45, 75, 90, 802, 24, 2, 66]; matriz ordenada final = radixSort (matriz); imprimir (matriz ordenada); } // Este código es una contribución de beeduhboodee>
Producción
2 24 45 66 75 90 170 802>
Análisis de complejidad de Radix Sort :
Complejidad del tiempo:
- Radix sort es un algoritmo de clasificación de enteros no comparativo que clasifica datos con claves enteras agrupando las claves por dígitos individuales que comparten la misma posición y valor significativos. Tiene una complejidad temporal de O(d * (n + b)) , donde d es el número de dígitos, n es el número de elementos y b es la base del sistema numérico que se utiliza.
- En implementaciones prácticas, la clasificación por base suele ser más rápida que otros algoritmos de clasificación basados en comparaciones, como la clasificación rápida o la clasificación por combinación, para conjuntos de datos grandes, especialmente cuando las claves tienen muchos dígitos. Sin embargo, su complejidad temporal crece linealmente con el número de dígitos, por lo que no es tan eficiente para conjuntos de datos pequeños.
Espacio Auxiliar:
- El tipo Radix también tiene una complejidad espacial de O(norte + segundo), donde n es el número de elementos y b es la base del sistema numérico. Esta complejidad del espacio proviene de la necesidad de crear depósitos para cada valor de dígito y copiar los elementos nuevamente a la matriz original después de ordenar cada dígito.
Preguntas frecuentes sobre RadixSort
P1. ¿Es preferible Radix Sort a los algoritmos de clasificación basados en comparación como Quick-Sort?
Si tenemos registro2n bits por cada dígito, el tiempo de ejecución de Radix parece ser mejor que Quick Sort para una amplia gama de números de entrada. Los factores constantes ocultos en la notación asintótica son mayores para Radix Sort y Quick-Sort utiliza cachés de hardware de manera más efectiva. Además, la clasificación Radix utiliza la clasificación por conteo como una subrutina y la clasificación por conteo requiere espacio adicional para ordenar los números.
P2. ¿Qué pasa si los elementos están en el rango de 1 a n 2 ?
expresión regular java para
- El límite inferior para el algoritmo de clasificación basado en comparación (clasificación por combinación, clasificación en montón, clasificación rápida, etc.) es Ω (nLogn), es decir, no pueden hacerlo mejor que nIniciar sesión . La ordenación por conteo es un algoritmo de ordenación en tiempo lineal que ordena en tiempo O(n+k) cuando los elementos están en el rango de 1 a k.
- No podemos usar la ordenación por conteo porque la ordenación por conteo tomará O(n2) que es peor que los algoritmos de clasificación basados en comparaciones. ¿Podemos ordenar tal matriz en tiempo lineal?
- Radix Suerte es la respuesta. La idea de Radix Sort es realizar una clasificación dígito por dígito comenzando desde el dígito menos significativo hasta el dígito más significativo. La ordenación por Radix utiliza la ordenación por conteo como una subrutina para ordenar.