algorithm - pseudocódigo - radix sort prueba de escritorio

¿Cómo funciona Radix Sort?

Question

No sé por qué es tan difícil para mí entenderlo. He revisado las páginas de la wiki y el pseudocódigo (así como el código real) tratando de comprender cómo funcionan los algoritmos de ordenación de radix (con respecto a los segmentos).

¿Estoy buscando algo equivocado aquí? ¿Debo buscar en el tipo de cubo, tal vez? ¿Puede alguien darme una versión simplificada de cómo funciona? Como referencia, aquí hay un bloque de código que supuestamente realiza una ordenación de radix:

// Sort ''size'' number of integers starting at ''input'' according to the ''digit''th digit
// For the parameter ''digit'', 0 denotes the least significant digit and increases as significance does
void radixSort(int* input, int size, int digit)
{
    if (size == 0)
        return;

    int[10] buckets;    // assuming decimal numbers

    // Sort the array in place while keeping track of bucket starting indices.
    // If bucket[i] is meant to be empty (no numbers with i at the specified digit),
    // then let bucket[i+1] = bucket[i]

    for (int i = 0; i < 10; ++i)
    {
        radixSort(input + buckets[i], buckets[i+1] - buckets[i], digit+1);
    }
}

Y también he analizado soluciones no recursivas:

void radixsort(int *a, int arraySize)
{
    int i, bucket[sortsize], maxVal = 0, digitPosition =1 ;
    for(i = 0; i < arraySize; i++) {
        if(a[i] > maxVal) maxVal = a[i];
    }

    int pass = 1; 
    while(maxVal/digitPosition > 0) {
        // reset counter 
        int digitCount[10] = {0};

        // count pos-th digits (keys) 
        for(i = 0; i < arraySize; i++)
            digitCount[a[i]/digitPosition%10]++;

        // accumulated count 
        for(i = 1; i < 10; i++)
            digitCount[i] += digitCount[i-1];

        // To keep the order, start from back side
        for(i = arraySize - 1; i >= 0; i--)
            bucket[--digitCount[a[i]/digitPosition%10]] = a[i];

        for(i = 0; i < arraySize; i++)
            a[i] = bucket[i];

        cout << "pass #" << pass++ << ": ";
        digitPosition *= 10;
    } 

}

Específicamente, esta línea me está dando problemas. Intenté recorrerlo con lápiz y papel, pero todavía no puedo entender lo que está haciendo:

   // To keep the order, start from back side
        for(i = arraySize - 1; i >= 0; i--)
            bucket[--digitCount[a[i]/digitPosition%10]] = a[i];

Answer 1

En matemáticas, radix significa base, donde decimal sería base 10. Imagine que tiene números, algunos de los cuales tienen más de un dígito, como

5, 213, 55, 21, 2334, 31, 20, 430

Para simplificar, supongamos que quiere usar la base decimal (= 10) para ordenar. Entonces comenzarías separando los números por unidades y luego juntándolos nuevamente; luego separarías los números por decenas y luego los juntarías de nuevo; luego por cientos y así sucesivamente hasta que todos los números estén ordenados. Cada vez que bucle, simplemente lea la lista de izquierda a derecha. También puedes imaginar que estás separando los números en cubos. Aquí hay una ilustración usando 5, 213, 55, 21, 2334, 31, 20, 430

Separado por unidades:

• ceros: 20, 430

• unos: 21, 31

• dos:

• tres en tres: 213

• Cuatro patas: 2334

• cinco: 5, 55

  De vuelta juntos: 20, 430, 21, 31, 213, 2334, 5, 55

Para volver a armarlos, primero lea el cubo de zeroes , luego ones balde, y así sucesivamente, hasta que lea el cucharón de nines .

Separados por decenas:

• ceros: 05

• unos: 213

• Dos: 20, 21

• tres: 430, 31, 2334,

• Cuatro:

• cinco: 55

  De vuelta juntos: 5, 213, 20, 21, 430, 31, 2334, 55

Separados por cientos:

• ceros: 005, 020, 021, 031, 055

• unos:

• Dos: 213

• tres: 2334

• Cuatro patas: 430

• cinco:

  De vuelta juntos: 5, 20, 21, 31, 55, 213, 2334, 430

Separados por miles:

• ceros: 0005, 0020, 0021, 0031, 0055, 0213, 0430

• unos:

• Dos: 2334

• tres:

• Cuatro:

• cinco:

  De vuelta juntos: 5, 20, 21, 31, 55, 213, 430, 2334

Ya has terminado. Vi un buen código para esto en Geekviewpoint tanto en Java como en python

Answer 2

Este es el flujo básico de quicksort.

Para el 1er pase: ordenamos el conjunto en función del dígito menos significativo (lugar 1) usando el tipo de conteo. Observe que 435 está por debajo de 835, porque 435 ocurrió por debajo de 835 en la lista original.

Para el segundo pase: ordenamos el conjunto sobre la base del siguiente dígito (lugar 10) usando el tipo de conteo. Observe que aquí 608 está por debajo de 704, porque 608 ocurrió por debajo de 704 en la lista anterior, y de manera similar por (835, 435) y (751, 453).

Para el tercer pase: ordenamos el conjunto sobre la base del dígito más significativo (lugar 100) usando el tipo de conteo. Observe que aquí 435 está por debajo de 453, porque 435 ocurrió por debajo de 453 en la lista anterior, y de manera similar por (608, 690) y (704, 751).

Para más detalles , puede consultar este blog en codingeek y tener una comprensión clara .

Answer 3

Piensa en un mazo de cartas. Primero lo clasifica por palo en cuatro montones. Luego colocas esas cuatro pilas una encima de la otra y ahora clasificas en 13 pilas según el rango. Ponlos juntos y ahora tienes un mazo ordenado.