Ordenamiento de radix con el uso de la cola

Question

He querido crear una implementación de radix sort usando colas.

No pude determinar qué parte de mi código tiene problemas o qué recursos debo leer. Mi código puede ser totalmente incorrecto, pero esta es mi implementación sin ayuda (aún no he tomado un curso de algoritmos de estructuras de datos &).

Creé una función pero no funcionó. Mientras investigaba, vi algunos ejemplos de código pero parecían ser más complejos para mí.

En primer lugar quería encontrar el dígito menos significativo de todos los enteros Entonces a clasificar en el elemento de la cola, cuyo subíndice partidos, continuación copia después de ordenar todas las colas al final de la cola de elementos 11. Haga esta ordenación en el 11º elemento de la cola nuevamente hasta alcanzar el dígito más significativo.

Pude encontrar el dígito menos significativo. Y ordena de acuerdo con este dígito. Pero no pude analizar otros dígitos. Por ejemplo; Pude ordenar 1, 2, 4, 5, 3 pero cuando llega el momento de ordenar 2 o más dígitos, falla ...

Espero, fui claro y expliqué mi problema brevemente.

// My function declaration 
// Pre: arrInts holds the linked list of integers which are going to be sort. 
// Post: queue will return result and its 11th element should hold sorted integers in 
//  that queue 
queue_node_t * radixSort(const queue_node_t *arrInts, queue_t *queue[], int size){ 
    queue_node_t *curNodep = arrInts; // Node to be checked 
    int i, curNum = curNodep->element.key; 
    if(curNodep == NULL){ 
     // If there is no other node left then assign them into 11th queue. 
     for(i=0;i<=9;i++){ 
      if(queue[i]->rearp!=NULL){ 
       if(queue[10]->size == 0){ 
        queue[10]->rearp = (queue_node_t *)malloc (sizeof(queue_node_t)); 
        queue[10]->frontp = queue[10]->rearp; 
       } else { 
        queue[10]->rearp->restp = (queue_node_t *)malloc(sizeof(queue_node_t)); 
        queue[10]->rearp = queue[10]->rearp->restp; 
       } 
       queue[10]->rearp = queue[i]->rearp; 
       queue[10]->size += queue[i]->size; 
      } 
     } 
     queue[10]->rearp = radixSort(queue[10]->rearp, queue, size); 
    } else { 
       // I used switch statement to handle least significant digit 
     switch(curNum%10){ 
     case 0: 
      if(queue[0]->size == 0){ 
       queue[0]->rearp = (queue_node_t *)malloc (sizeof(queue_node_t)); 
       queue[0]->frontp = queue[0]->rearp; 
      } else { 
       queue[0]->rearp->restp = (queue_node_t *)malloc(sizeof(queue_node_t)); 
       queue[0]->rearp = queue[0]->rearp->restp; 
      } 
      ++(queue[0]->size); 
      queue[0]->rearp->element = curNodep->element; 
      queue[0]->rearp->restp = NULL; 
      radixSort(curNodep->restp, queue, size); 
      break; 
     case 1: 
      if(queue[1]->size == 0){ 
       queue[1]->rearp = (queue_node_t *)malloc (sizeof(queue_node_t)); 
       queue[1]->frontp = queue[0]->rearp; 
      } else { 
       queue[1]->rearp->restp = (queue_node_t *)malloc(sizeof(queue_node_t)); 
       queue[1]->rearp = queue[1]->rearp->restp; 
      } 
      ++(queue[1]->size); 
      queue[1]->rearp->element = curNodep->element; 
      queue[1]->rearp->restp = NULL; 
         // I tried to make recursion but I guess this is one the problems 
      radixSort(curNodep->restp, queue, size); 
      break; 
     case 2: 
      if(queue[2]->size == 0){ 
       queue[2]->rearp = (queue_node_t *)malloc (sizeof(queue_node_t)); 
       queue[2]->frontp = queue[2]->rearp; 
      } else { 
       queue[2]->rearp->restp = (queue_node_t *)malloc(sizeof(queue_node_t)); 
       queue[2]->rearp = queue[2]->rearp->restp; 
      } 
      ++(queue[2]->size); 
      queue[2]->rearp->element = curNodep->element; 
      queue[2]->rearp->restp = NULL; 
      radixSort(curNodep->restp, queue, size); 
      break; 
     case 3: 
      if(queue[3]->size == 0){ 
       queue[3]->rearp = (queue_node_t *)malloc (sizeof(queue_node_t)); 
       queue[3]->frontp = queue[3]->rearp; 
      } else { 
       queue[3]->rearp->restp = (queue_node_t *)malloc(sizeof(queue_node_t)); 
       queue[3]->rearp = queue[3]->rearp->restp; 
      } 
      ++(queue[3]->size); 
      queue[3]->rearp->element = curNodep->element; 
      queue[3]->rearp->restp = NULL; 

      queue[10]->rearp = radixSort(curNodep->restp, queue, size); 
      break; 
     case 4: 
      if(queue[4]->size == 0){ 
       queue[4]->rearp = (queue_node_t *)malloc (sizeof(queue_node_t)); 
       queue[4]->frontp = queue[4]->rearp; 
      } else { 
       queue[4]->rearp->restp = (queue_node_t *)malloc(sizeof(queue_node_t)); 
       queue[4]->rearp = queue[4]->rearp->restp; 
      } 
      ++(queue[4]->size); 
      queue[4]->rearp->element = curNodep->element; 
      queue[4]->rearp->restp = NULL; 
      radixSort(curNodep->restp, queue, size); 
      break; 
     case 5: 
      if(queue[5]->size == 0){ 
       queue[5]->rearp = (queue_node_t *)malloc (sizeof(queue_node_t)); 
       queue[5]->frontp = queue[5]->rearp; 
      } else { 
       queue[5]->rearp->restp = (queue_node_t *)malloc(sizeof(queue_node_t)); 
       queue[5]->rearp = queue[5]->rearp->restp; 
      } 
      ++(queue[5]->size); 
      queue[5]->rearp->element = curNodep->element; 
      queue[5]->rearp->restp = NULL; 

      radixSort(curNodep->restp, queue, size); 
      break; 
     case 6: 
      if(queue[6]->size == 0){ 
       queue[6]->rearp = (queue_node_t *)malloc (sizeof(queue_node_t)); 
       queue[6]->frontp = queue[6]->rearp; 
      } else { 
       queue[6]->rearp->restp = (queue_node_t *)malloc(sizeof(queue_node_t)); 
       queue[6]->rearp = queue[6]->rearp->restp; 
      } 
      ++(queue[6]->size); 
      queue[6]->rearp->element = curNodep->element; 
      queue[6]->rearp->restp = NULL; 

      radixSort(curNodep->restp, queue, size); 
      break; 
     case 7: 
      if(queue[7]->size == 0){ 
       queue[7]->rearp = (queue_node_t *)malloc (sizeof(queue_node_t)); 
       queue[7]->frontp = queue[7]->rearp; 
      } else { 
       queue[7]->rearp->restp = (queue_node_t *)malloc(sizeof(queue_node_t)); 
       queue[7]->rearp = queue[7]->rearp->restp; 
      } 
      ++(queue[7]->size); 
      queue[7]->rearp->element = curNodep->element; 
      queue[7]->rearp->restp = NULL; 

      radixSort(curNodep->restp, queue, size); 
      break; 
     case 8: 
      if(queue[8]->size == 0){ 
       queue[8]->rearp = (queue_node_t *)malloc (sizeof(queue_node_t)); 
       queue[8]->frontp = queue[8]->rearp; 
      } else { 
       queue[8]->rearp->restp = (queue_node_t *)malloc(sizeof(queue_node_t)); 
       queue[8]->rearp = queue[8]->rearp->restp; 
      } 
      ++(queue[8]->size); 
      queue[8]->rearp->element = curNodep->element; 
      queue[8]->rearp->restp = NULL; 

      radixSort(curNodep->restp, queue, size); 
      break; 
     case 9: 
      if(queue[9]->size == 0){ 
       queue[9]->rearp = (queue_node_t *)malloc (sizeof(queue_node_t)); 
       queue[9]->frontp = queue[9]->rearp; 
      } else { 
       queue[9]->rearp->restp = (queue_node_t *)malloc(sizeof(queue_node_t)); 
       queue[9]->rearp = queue[9]->rearp->restp; 
      } 
      ++(queue[9]->size); 
      queue[9]->rearp->element = curNodep->element; 
      queue[9]->rearp->restp = NULL; 

      radixSort(curNodep->restp, queue, size); 
      break; 
     } 
    } 

    return queue[10]->rearp; 
} 

Edición 1 (hecho algunos progresos)

he seguido las sugerencias de William Morris. Tuve que hacer la misma pregunta en CodeReview y él me dio algunas instrucciones para que mi código fuera más claro.

Dividí mi función en funciones y también detuve la recurrencia.

En primer lugar, he creado una función add_to_q que añade valor a la cola relacionada y que ayudó a librarse de la duplicación de código. Por cierto, el camino de James Khoury es el más simple, pero nuevamente utiliza la recursión.

void add_to_q(queue_t *queue_arr[], int value, int pos) { 
if(queue_arr[pos]->size == 0){ 
    queue_arr[pos]->rearp = (queue_node_t *)malloc (sizeof(queue_node_t)); 
    queue_arr[pos]->frontp = queue_arr[pos]->rearp; 
} else { 
    queue_arr[pos]->rearp->restp = (queue_node_t *)malloc(sizeof(queue_node_t)); 
    queue_arr[pos]->rearp = queue_arr[pos]->rearp->restp; 
} 
queue_arr[pos]->rearp->element = value; 
queue_arr[pos]->size++; 
} 

En segundo lugar creé otras funciones auxiliares. Uno es add_to_eleventh que simplemente agrega todos los elementos de cola a la cola de la undécima fila. En mi opinión, está haciendo lo que quiere la pregunta.

queue_t * add_to_eleventh(queue_t *queue[]) { 
int i; 
for(i=0;i<=9;i++){ 
    while(queue[i]->frontp != NULL){ 
     if(queue[10]->size == 0){ 
      queue[10]->rearp = (queue_node_t *)malloc (sizeof(queue_node_t)); 
      queue[10]->frontp = queue[10]->rearp; 
     } else { 
      queue[10]->rearp->restp = (queue_node_t *)malloc(sizeof(queue_node_t)); 
      queue[10]->rearp = queue[10]->rearp->restp; 
     } 
     if (queue[i]->size != 0){ 
      queue[10]->rearp->element = queue[i]->frontp->element; 
      printf("---%d***",queue[i]->frontp->element); 
     } 
     queue[10]->size+=1; 
     queue[i]->frontp = queue[i]->frontp->restp; 
     queue[10]->rearp->restp = NULL; 
    } 
} 
return queue[10]; 
} 

En tercer lugar, mi última función auxiliar es back_to_ints. Su propósito es tomar los elementos en la cola 11 y dividirlos por diez y devolverlos en una matriz de enteros.

void back_to_ints(queue_t *arr[], int *new_arr) { 
queue_node_t *cur_nodep; 
cur_nodep = arr[10]->frontp; 
int i = 0, digit; 
while(cur_nodep != NULL){ 
    cur_nodep->element/=10; 
    digit = cur_nodep->element/10; 
    new_arr[i++] = digit; 
    cur_nodep = cur_nodep->restp; 
} 
} 

Finalmente mi nueva función de clasificación que es ahora ordena los números enteros en mismo dígito. Tal que, los números [7] = {112,133,122,334,345,447,346};

queue_t * radix_sort(int *arr, const int size,queue_t *sorted_arr[]) { 
int i, digit[size], initials[size],j; 
for(i=0;i<size;i++) 
    initials[i] = arr[i]; 
i = 0; 
while(initials[i] != 0){ 
    j = i; 
    printf("initialssss%d", initials[--j]); 
    back_to_ints(sorted_arr, initials); 

    for(i=0;i<size;i++){ 
    digit[i] = initials[i] % 10; 

    switch (digit[i]) { 
    case 0: 
     add_to_q(sorted_arr, arr[i], 0); 
     break; 
    case 1: 
     add_to_q(sorted_arr, arr[i], 1); 
     break; 
    case 2: 
     add_to_q(sorted_arr, arr[i], 2); 
     break; 
    case 3: 
     add_to_q(sorted_arr, arr[i], 3); 
     break; 
    case 4: 
     add_to_q(sorted_arr, arr[i], 4); 
     break; 
    case 5: 
     add_to_q(sorted_arr, arr[i], 5); 
     break; 
    case 6: 
     add_to_q(sorted_arr, arr[i], 6); 
     break; 
    case 7: 
     add_to_q(sorted_arr, arr[i], 7); 
     break; 
    case 8: 
     add_to_q(sorted_arr, arr[i], 8); 
     break; 
    case 9: 
     add_to_q(sorted_arr, arr[i], 9); 
     break; 
     } 
    } 
    sorted_arr[10] = add_to_eleventh(sorted_arr); 
    i++; 
} 
return sorted_arr[10]; 
} 

He resuelto parcialmente la cuestión. Si desea ordenar los números en el mismo dígito, funciona. De lo contrario, falla. Por ejemplo, sus entradas son 112,133,122,334,345,447,346, entonces el resultado será .Pero, si el usuario quiere ordenar algo así (111,13,12,334,345,447,1), da . Entonces, ¿cómo puedo superar este problema?

Además, he cambiado un poco el archivo de encabezado.

#ifndef RADIX_H_ 
#define RADIX_H_ 

typedef struct queue_node_s { 
    int element; 
    struct queue_node_s *restp; 
}queue_node_t; 

typedef struct { 
    queue_node_t *frontp, 
      *rearp; 
    int size; 
}queue_t; 

queue_t * radix_sort(int *arr,const int size, queue_t *sorted_arr[]); 
void add_to_q(queue_t *queue_arr[], int value, int pos); 
queue_t * add_to_eleventh(queue_t *queue[]); 
void back_to_ints(queue_t *arr[], int *new_arr); 
void displayRadixed(queue_t *sorted[]); 
#endif /* RADIX_H_ */ 

Gracias por volver a abrir mi hilo ...

Answer 1

Negación: no he implementado una especie radix antes o probado el código de abajo. Te lo dejo como ejercicio.

Cuando se encuentre copiando y pegando algo más de una vez, pare y piense: debe haber un patrón.

Su declaración de cambio es una gran cantidad de copiar y pegar. En case 1: tiene una línea:

queue[1]->frontp = queue[0]->rearp; 

supongo que debe ser:

queue[1]->frontp = queue[1]->rearp; 

Si había re-factorizado este código es posible que haya sido capaz de ver esto más fácil?

¿Qué pasa con la sustitución de toda la instrucción switch con:

int leastSignificantDigit = curNum%10; 

if(queue[leastSignificantDigit]->size == 0){ 
    queue[leastSignificantDigit]->rearp = (queue_node_t *)malloc (sizeof(queue_node_t)); 
    queue[leastSignificantDigit]->frontp = queue[leastSignificantDigit]->rearp; 
} else { 
    queue[leastSignificantDigit]->rearp->restp = (queue_node_t *)malloc(sizeof(queue_node_t)); 
    queue[leastSignificantDigit]->rearp = queue[leastSignificantDigit]->rearp->restp; 
} 
++(queue[leastSignificantDigit]->size); 
queue[leastSignificantDigit]->rearp->element = curNodep->element; 
queue[leastSignificantDigit]->rearp->restp = NULL; 
radixSort(curNodep->restp, queue, size); 

Answer 2

El problema que he visto en el primer ejemplo de código es que

curNum = curNodep-> element.key

curNum siempre tiene el número completo y la instrucción de cambio siempre lo hace curNum% 10, y esto solo prueba el último dígito.

En su solución de recursión (la recursión no es un problema) debe pasar un parámetro para saber cuál es el dígito que tiene que tratar.

Conozco esta técnica como inmersión.

Si ve las muestras que pone al final de la respuesta, puede ver que el último dígito es orderer, puede cambiar las muestras de entrada para ver mejor esto. Agregue números grandes con un último número pequeño, por ejemplo '901', y vea el resultado.

Lo siento por mi inglés ...

Answer 3

He modificado un poco la cola. Para entender mejor el código, utilizo el frente y la parte posterior como variables globales.

typedef struct queue *queue_ptr; 
     struct queue { 
       int data; 
       queue_ptr next; 
     }; 
queue_ptr front[10], rear[10]; /* For base 10, The 11th queue is not needed */ 

lo que la operación de añadir a la cola se convierte en

void add_queue(int i, int data) { 
     queue_ptr tmp; 

     tmp = (queue_ptr) malloc(sizeof(*tmp)); 
     tmp->next = NULL; 
     tmp->data = data; 
     if (front[i]) { 
       rear[i]->next = tmp; 
     } else { 
       front[i] = tmp; 
     } 
     rear[i] = tmp; 
} 

y añadir una operación de borrar de una cola (devolver los datos así)

int delete_queue(int i) { 
     int data; 
     queue_ptr tmp; 

     tmp = front[i]; 
     if (!tmp) { 
       return -1; /* So that we can check if queue is empty */ 
     } 
     data = tmp->data; 
     front[i] = tmp->next; 
     free(tmp); 
     return data; 
} 

Así que ahora podemos poner en práctica el tipo de raíz. Puede ser más fácil mover sus datos a la cola con los números reales en lugar de un solo dígito.Tenga en cuenta que no se necesita la cola de 11 si se puede modificar la matriz de prueba * arr, y su función radix_sort podría ser así:

void radix_sort(int *arr, const int size) { 
     int i, j, k, radix, digits, tmp; 

     if (size < 1) { 
       return; /* don't do anything if invalid size */ 
     } 

     /* get the number of digits */ 
     for (digits = 0, radix = 1; arr[0] >= radix; digits++, radix *= 10); 

     /* perform sort (digits) times from LSB to MSB */ 
     for (i = 0, radix = 1; i < digits; i++, radix *= 10) { 
       /* distribute into queues */ 
       for (j = 0; j < size; j++) { 
         add_queue((arr[j]/radix) % 10, arr[j]); 
       } 
       /* take them out from each queue to the original test array */ 
       for (j = 0, k = 0; j < 10; j++) { 
         for (tmp = delete_queue(j); tmp != -1;\ 
          tmp = delete_queue(j), k++) { 
           arr[k] = tmp; 
         } 
       } 
     } 
} 

Y finalmente puede probar llamando radix_sort (your_array, your_array_size), el pleno código es

#include <stdio.h> 
#include <stdlib.h> 

typedef struct queue *queue_ptr; 
     struct queue { 
       int data; 
       queue_ptr next; 
     }; 

queue_ptr front[10], rear[10]; /* For base 10, The 11th queue is not needed */ 

void add_queue(int i, int data) { 
     queue_ptr tmp; 

     tmp = (queue_ptr) malloc(sizeof(*tmp)); 
     tmp->next = NULL; 
     tmp->data = data; 
     if (front[i]) { 
       rear[i]->next = tmp; 
     } else { 
       front[i] = tmp; 
     } 
     rear[i] = tmp; 
} 

int delete_queue(int i) { 
     int data; 
     queue_ptr tmp; 

     tmp = front[i]; 
     if (!tmp) { 
       return -1; /* So that we can check if queue is empty */ 
     } 
     data = tmp->data; 
     front[i] = tmp->next; 
     free(tmp); 
     return data; 
} 

void radix_sort(int *arr, const int size) { 
     int i, j, k, radix, digits, tmp; 

     if (size < 1) { 
       return; /* don't do anything if invalid size */ 
     } 

     /* get the number of digits */ 
     for (digits = 0, radix = 1; arr[0] >= radix; digits++, radix *=10); 

     /* perform sort (digits) times from LSB to MSB */ 
     for (i = 0, radix = 1; i < digits; i++, radix *= 10) { 
       /* distribute to queues */ 
       for (j = 0; j < size; j++) { 
         add_queue((arr[j]/radix) % 10, arr[j]); 
       } 
       /* take them out from each queue to the original test array */ 
       for (j = 0, k = 0; j < 10; j++) { 
         for (tmp = delete_queue(j); tmp != -1;\ 
          tmp = delete_queue(j), k++) { 
           arr[k] = tmp; 
         } 
       } 
     } 
} 

int main(void) { 
     int i; 
     int a[5] = {133, 34, 555, 111, 12}, 
      b[12] = {1, 1, 1, 4, 5, 6, 7, 8, 9, 11, 11, 12}; 

     radix_sort(a, 5); 
     radix_sort(b, 5); 

     for (i = 0; i < 5; i++) { 
       printf("%d ", a[i]); 
     } 
     printf("\n"); 

     for (i = 0; i < 12; i++) { 
       printf("%d ", b[i]); 
     } 
     printf("\n"); 

     return 0; 
} 

y la salida es

12 34 111 133 555 
1 1 1 4 5 6 7 8 9 11 11 12 

Answer 4

una buena información ya aquí. En un nivel superior, será difícil depurar el código porque es más complejo de lo que debe ser. A continuación se muestra un código diferente que utiliza C para expresar el algoritmo en un estilo más idiomático.

El punto general es que cuando se trata de código, menos suele ser más: la simplicidad es tu amiga. Características que se muestran aquí:

1. Listas de enlace único para las colas. Una cola es un puntero al nodo de cola de la lista. Con esto, anexar y concatenar son operaciones rápidas de tiempo constante.
2. Descomposición funcional lógica y reutilizable.
3. Solo aproximadamente 80 SLOC incluyendo una prueba simple. La función de clasificación es 18 SLOC.
4. Ligeramente probado.

Aquí es el tipo:

// Radix sort the given queue. 
void sort(QUEUE *queue) 
{ 
    unsigned i, j, div; 
    QUEUE queues[RADIX], accum; 

    // Handle case of nothing to sort. 
    if (*queue == NULL) return; 

    // Accumulator queue initially holds unsorted input. 
    accum = *queue; 

    // Make one pass per radix digit. 
    for (i = 0, div = RADIX; i < MAX_DIGITS; i++, div *= RADIX) { 

    // Clear the radix queues. 
    for (j = 0; j < RADIX; j++) queues[j] = NULL; 

    // Append accumulator nodes onto radix queues based on current digit. 
    NODE *p = accum, *p_next = p->next; 
    do { 
     // Save p->next here because append below will change it. 
     p = p_next; p_next = p->next; 
     append_node(&queues[p->val/div % RADIX], p); 
    } while (p != accum); 

    // Gather all the radix queues into the accumulator again. 
    for (accum = NULL, j = 0; j < RADIX; j++) cat(&accum, queues[j]); 
    } 
    // Accumulator now holds sorted input. 
    *queue = accum; 
} 

Y el resto:

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 

#define RADIX 10 
#define MAX_DIGITS 9 

// Node and circular queue. A queue is either null or a pointer to the _tail_ node. 
typedef struct node_s { 
    struct node_s *next; 
    unsigned val; 
} NODE, *QUEUE; 

// Make a new node with given value. 
NODE *new_node(unsigned val) 
{ 
    NODE *node = calloc(1, sizeof *node); 
    // Must trap null return value here in production code! 
    node->val = val; 
    return node; 
} 

// Append given node to the tail of a queue. 
void append_node(QUEUE *queue, NODE *node) 
{ 
    NODE *tail = *queue; 
    if (tail) { 
    node->next = tail->next; 
    tail->next = node; 
    } 
    else { 
    node->next = node; 
    } 
    *queue = node; 
} 

// Concatenate the second queue onto the tail of the first. 
// First queue is changed (because it's a pointer to a tail node). 
void cat(QUEUE *a, QUEUE b_tail) 
{ 
    NODE *a_tail, *a_head; 

    if (b_tail == NULL) return; 
    a_tail = *a; 
    if (a_tail) { 
    a_head = a_tail->next; 
    a_tail->next = b_tail->next; 
    b_tail->next = a_head; 
    } 
    *a = b_tail; 
} 
// Sort code above goes here if you're compiling it. 
// And test main goes here. 

Una pequeña prueba principal:

int main(void) 
{ 
    int i; 
    unsigned data[] = { 98, 111, 42, 1111, 21 , 997, 0, 99999, 20903}; 

    // Make a queue from data. 
    QUEUE a = NULL; 
    for (i = 0; i < sizeof data/sizeof data[0]; i++) 
    append_node(&a, new_node(data[i])); 

    sort(&a); 

    // Print the circular list. 
    NODE *p = a; 
    do { 
    p = p->next; 
    printf("%u\n", p->val); 
    } while (p != a); 

    return 0; 
}