algorithm - para - ¿Cuál es la diferencia entre ordenar por cubo y ordenar por radix?
radix sort en c (2)
El tipo de cubo y el tipo de raíz son primos cercanos; la ordenación del cucharón va de MSD a LSD, mientras que la ordenación de radix puede ir en ambas "direcciones" (LSD o MSD). ¿Cómo funcionan ambos algoritmos, y en particular, cómo difieren?
Bucket Sort y Radix Sort son como algoritmos de clasificación hermanos porque no son géneros de comparación y la idea general es similar. Además, ambos son un poco abstractos en la implementación.
Radix Sort :
Radix significa base (binario, octal, decimal, etc.). Por lo tanto, esta clasificación es para números (también se usa para cadenas). Esto funciona cuando cada elemento E es como e k ... e 2 e 1 e 0 , donde e i está en algún rango. (generalmente 0 a una base como 0-9 en decimal o 0-255 en caracteres ASCII)
A continuación, utiliza k pasadas de un algoritmo de subordenación estable ( tiene que ser estable o de lo contrario no funciona el ordenamiento de Radix) para ordenar los números. Este algoritmo de clasificación secundaria suele ser Clasificación de conteo o Clasificación de categoría, pero no puede ser de clasificación de Radix .
Puede comenzar desde el Dígito más Significativo o el Dígito Menos Significativo porque mezcla todos los números en cada pasada (de k a 0 o de 0 a k)
Es un algoritmo de clasificación estable .
Clasificación del cubo:
Separa la matriz en grupos o cubos más pequeños y los ordena individualmente mediante un algoritmo de clasificación secundaria o llamada recursiva a sí mismo y luego combina el resultado . Por ejemplo, ordenando jugadores agregándolos a los cubos de su equipo y luego clasificándolos por los números de su jersey o algo así como clasificando números del 1-30 en 3 cubos de 1-10, 11-20, 21-30.
El paso combinado es trivial (a diferencia del tipo de fusión). solo copie los elementos de cada cubo de nuevo en el conjunto original o únase al encabezado de cada segmento con el extremo del depósito anterior (en el caso de las listas vinculadas)
Radix / base podría ser un tipo / instancia del grupo / cubo al ordenar números. Por lo tanto, se podría pensar en MSD radix como una instancia modificada de clasificación de cubo
El ordenamiento del cubo no está en el lugar, pero es un algoritmo de clasificación estable . Sin embargo, algunas variaciones de la clasificación del depósito pueden no ser estables (si usa un algoritmo de ordenamiento secundario que no es estable)
El pase inicial de RadixSort y BucketSort es exactamente el mismo. Los elementos se colocan en buckets (o bins ) de rangos incrementales (por ejemplo, 0-10, 11-20, ... 90-100), dependiendo de la cantidad de dígitos en el número más grande.
En la siguiente pasada, sin embargo, BucketSort ordena estos ''cubos'' y los agrega en una matriz. Sin embargo, RadixSort agrega las cubetas sin clasificación adicional y las ''re-cubetas'' basándose en el segundo dígito (el lugar de las diez) de los números. Por lo tanto, BucketSort es más eficiente para las matrices ''densas'', mientras que RadixSort puede manejar bien las matrices dispersas (bueno, no exactamente dispersas, pero espaciadas).