Radix Sort

Una radix o base es una representación de un número que muestra cuántos dígitos se requieren para representar un número posicional. Por ejemplo, para representar el número binario, el valor de Radix es 2 (representamos el binario con 0 o 1). Para representar el número decimal, el valor de Radix es 10 (representamos el número decimal con números 0 a 9).

Cómo funciona el algoritmo de clasificación redix

Supongamos que tenemos la siguiente lista de matriz y queremos clasificar esta matriz usando el sort Radix:

Usamos dos conceptos más en este algoritmo, que son:

1. 1. Dígito menos significativo
   2. Dígito más significativo

1. Dígito menos significativo (LSD): El valor exponente de un número decimal que está extremadamente cerca de la posición más derecha se conoce como el LSD.

Por ejemplo, el número decimal "2563" tiene el valor de dígitos menos significativo de "3".

2. Dígito más significativo (MSD): El MSD es el inverso exacto del LSD. Un valor de MSD es el dígito más no cero de la izquierda de cualquier número decimal.

Por ejemplo, el número decimal "2563" tiene el valor de dígitos más significativo de "2".

Paso 1: busque el elemento más importante (valor máximo)

Como ya sabemos, este algoritmo funciona en los dígitos para ordenar los números. Entonces, para eso, este algoritmo requiere el número máximo de dígitos para la iteración. Nuestro primer paso es averiguar el número máximo de elementos en esta matriz. Después de encontrar el valor máximo de una matriz, tenemos que contar el número de dígitos en ese número para las iteraciones.

Paso 2: Cuente el número de dígitos del elemento máximo

Tenemos que contar el número de dígitos del elemento máximo de una matriz porque entonces podemos averiguar cuántas iteraciones necesitamos para clasificar la matriz.

Entonces, como ya descubrimos, el elemento máximo es 167 y el número de dígitos es 3. Necesitamos tres iteraciones para clasificar la matriz.

Paso 3: Ordenar los elementos por dígito menos significativo

La disposición del primer dígito se realiza por el dígito menos significativo. A partir de la siguiente imagen, podemos ver que todos los dígitos más pequeños y menos significativos están dispuestos en el lado izquierdo. En este caso, nos centramos solo en el dígito menos significativo.

Una cosa más que podemos notar aquí es que algunos dígitos se clasifican automáticamente, incluso si sus dígitos unitarios son diferentes, pero los otros son iguales.

Por ejemplo, Los números 36 en la posición del índice 7 y el número 32 en la posición del índice 3 tienen diferentes dígitos unitarios pero tienen el mismo otro número, que es 3. Obviamente, el número 32 viene antes del número 36. Después de las disposiciones del primer elemento, podemos ver que ahora, 32 viene antes de 36, que se clasifica automáticamente.

Paso 4: Ordenar los elementos de acuerdo con el siguiente dígito (dígito de decenas)

Ahora, organizamos los elementos de la matriz a través del décimo dígito. Como ya sabemos, esta clasificación debe finalizarse en 3 iteraciones porque el número máximo de elementos tiene 3 dígitos. Esta es nuestra segunda iteración y podemos suponer que la mayoría de los elementos de la matriz se clasifican después de esta iteración.

Los resultados dados muestran que la mayoría de los elementos de la matriz ya están ordenados (por debajo de 100). Si solo tuviéramos dos dígitos como nuestro número máximo, solo dos iteraciones son suficientes para obtener la matriz ordenada.

Paso 5: Ordenar los elementos basados ​​en el dígito más significativo

Ahora, ingresamos a la tercera iteración basada en el dígito más significativo (cientos de lugar). Esta iteración clasifica los elementos de tres dígitos de la matriz. Después de esta iteración, todos los elementos de la matriz están en orden ordenado.

Después de organizar los elementos basados ​​en el MSD, nuestra matriz ahora está completamente ordenada.

Entendimos los conceptos del algoritmo de clasificación Radix. Pero necesitamos un algoritmo más para implementar el tipo Radix, y ese es el Algoritmo de clasificación de contabilidad. Entendamos esto Algoritmo de clasificación de contabilidad.

Algoritmo de clasificación de contabilidad

Ahora explicamos cada paso del algoritmo de clasificación de conteo.

La matriz proporcionada es nuestra matriz de entrada, y los números que se muestran arriba de la matriz son los números de índice de los elementos correspondientes.

Paso 1: busque el elemento máximo

El primer paso en el algoritmo de clasificación de conteo es buscar el elemento máximo en toda la matriz. La mejor manera de buscar el elemento máximo es atravesar toda la matriz y comparar los elementos en cada iteración: el elemento de valor mayor se actualiza hasta el final de la matriz.

Durante el primer paso, encontramos que el elemento MAX es 9 en la posición de índice 8.

Paso 2: hacer una nueva variedad de tamaños comparables

Creamos una nueva variedad de tamaños similares. Como ya sabemos, el valor máximo de la matriz es 9, por lo que habrá un total de 10 elementos. Como resultado, requerimos un tamaño de matriz máximo de + 1.

Como podemos ver en la imagen anterior, tenemos un tamaño de matriz total de 10 con valores de 0. En el siguiente paso, llenamos esta matriz de recuentos con elementos ordenados.

Paso 3: Llene la nueva matriz de acuerdo con la frecuencia de cada elemento

En este paso, contamos cada elemento y, de acuerdo con su frecuencia, llenamos los valores correspondientes en la matriz.

Por ejemplo, Como podemos ver, el elemento 6 está presente dos veces en la matriz de entrada. Entonces, ingresamos el valor de frecuencia de 2 en el índice 6.

Paso 4: Determinar la frecuencia acumulada

Ahora, contamos la frecuencia acumulativa de la matriz llena. Esta frecuencia acumulativa se usa más tarde para ordenar la matriz de entrada.

Podemos calcular la frecuencia acumulativa agregando el valor actual al valor del índice anterior, como se muestra en la siguiente captura de pantalla:

El último valor de la matriz en la matriz acumulada debe ser el número total de elementos.

Paso 5: Ordenar la matriz por frecuencia conmutativa

Ahora, usamos la matriz de frecuencia acumulativa para mapear cada elemento de matriz para producir una matriz ordenada.

Por ejemplo, el primer elemento en la matriz 5 que elegimos. Luego, el valor de frecuencia acumulativo correspondiente en el índice 5 que tiene un valor de 7. Disminuimos el valor en 1 y obtuvo 6. Colocamos el valor 5 en el índice en la posición 6 y también disminuimos la frecuencia acumulada en el índice 5 por 1.

La frecuencia acumulada está en el índice 5 después de ser disminuido por uno.

Entendamos este concepto con un ejemplo más.

El siguiente elemento en la matriz es 2. Elegimos el valor de índice de 2 en la matriz de frecuencia conmutativa. Disminuimos el valor en el índice 2 y obtenemos 1. Colocamos el elemento de matriz 2 en la posición del índice 1. Al final, disminuimos el valor de frecuencia en el índice 2 por 1, como se muestra en la siguiente captura de pantalla:

Desde la matriz ordenada anterior, podemos ver que solo queda un lugar antes de 2 (posición de índice 1) y un valor inferior a 2 en la matriz original, que es 1. Entonces, va de la manera correcta de clasificar la matriz.

No tenemos que recordar reducir el valor acumulativo en cada iteración. Después de dos de las iteraciones anteriores, la matriz acumulativa se parece a la siguiente:

Paso 6: matriz final

Ejecutamos el paso 5 hasta que cada elemento de matriz se llene en la matriz ordenada. Después de llenarse, nuestra matriz se ve así:

Programa C ++ para el algoritmo de clasificación de Radix

Este ejemplo se basa en la explicación en este tutorial de insinuos de Linux

#incluir
usando el espacio de nombres STD;
Void RadixSortalgo (int a [], int size_of_a)
// En el primer paso (paso 1), finificamos el valor máximo en la matriz.
int maximumnumber = a [0];
para (int i = 1; imaximumnumber = max (maximumnumber, a [i]);

// En el segundo paso (paso 2), estamos calculando el número de dígitos de
// El elemento máximo de la matriz
int digitsCount = 0;
while (maximumnumber> 0)
digitscount ++;
Maximumnumber /= 10;

// Ahora estamos actualizando una nueva matriz (pasos 3,4 y 5)
para (int i = 0; iint pwr = pow (10, i);
int new_a [size_of_a];
// Este es un count_array que se usa para la matriz de conteo
// para clasificar los dígitos de 0 a 9.
int count_array [10];
memset (count_array, 0, sizeof (count_array));
// Calcular la frecuencia de cada elemento de la matriz
para (int j = 0; jint num = (a [j]/pwr) % 10;
count_array [num] ++;

// Esta es una frecuencia cómica
para (int j = 1; j<10;j++)
count_array [j] += count_array [j-1];

// estamos mapeando la matriz de frecuencia con cada elemento
// de la matriz para encontrar la posición deseada en la matriz actualizada
for (int j = size_of_a-1; j> = 0; j-)
int num = (a [j]/pwr) % 10;
new_a [count_array [num] -1] = a [j];
count_array [num]-;

// Ahora, estamos actualizando la matriz con la nueva matriz
para (int j = 0; ja [j] = new_a [j];

// Finalmente, imprimimos el resultado de la matriz ordenado
para (int j = 0; jcout<cout<
int main ()
// Esta matriz de valores se ordenará utilizando el algoritmo de clasificación Radix.
int a [] = 155, 10, 51, 38, 16, 811, 755, 3, 91, 6;
// estamos calculando el tamaño de la matriz
int size_of_a = sizeof (a)/sizeof (size_of_a);
// Método de algoritmo de clasificación de Radix
radixsortalgo (a, size_of_a);
regresar 1;

Salida de ejecutar C+ Radix Sort

linuxhint@escritorio: ~ $ ./base
3 6 10 16 38 51 91 155 755 811
linuxhint@escritorio: ~ $

Complejidad del tiempo del algoritmo de clasificación de Radix

Calculemos la complejidad del tiempo del algoritmo de clasificación Radix.

Paso 1: para calcular el número máximo de elementos en toda la matriz, atravesamos toda la matriz. Entonces, el tiempo total requerido es o (n).

Paso 2: Supongamos que los dígitos totales en el número máximo es k. Entonces, el tiempo total que se toma para calcular el número de dígitos en un número máximo es o (k).

Pasos 3 a 5: Estos pasos funcionan en los dígitos en sí, por lo que toman O (k) veces junto con contar el algoritmo de clasificación en cada iteración - o (k * n).

Como resultado, la complejidad del tiempo total es o (k * n).

Conclusión

Estudiamos el algoritmo Radix Sort y contando. Hay diferentes tipos de algoritmos de clasificación que están disponibles en el mercado. El mejor algoritmo también depende de los requisitos. No es fácil decir qué algoritmo es mejor. Pero sobre la base de la complejidad del tiempo, estamos tratando de descubrir el mejor algoritmo. Y sobre la base de eso, Radix Sort también es uno de los mejores algoritmos para clasificar.