Radix Sorting with using queue

Question

I've wanted to create a radix sort implementation using queues.

I couldn't figure out which part of my code has problems or which resources should I read. My code may be totally wrong but this is my implementation without any help (I haven't taken a data structures & algorithms course yet).

I created a function but it didn't work. While doing research, I saw some code samples but they seemed to be more complex for me.

Firstly I wanted to find the least significant digit of all integers Then sort them in queue element whose subscript matches, then after sort copy all queues to end of 11th queue element. Do this sort in 11th queue element again until reach most significant digit.

I could find least significant digit. And sort according to this digit. But, I couldn't analyse other digits. For instance; I could sort 1, 2 , 4, 5, 3 but when time comes to sort 2 or more digits, it fails...

I hope, I was clear and explained my problem briefly.

// 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;
}

Edit 1 ( Made some progress )

I followed suggestions from William Morris. I had to ask same question on CodeReview and he gave me some instructions to make my code clearer.

I divided my function into functions and also stopped using recursion.

Firstly, I created a add_to_q function which adds value to related queue and it helped to get rid of code duplication. By the way James Khoury's way is simplest one but it again uses recursion.

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++;
}

Secondly I created other helper functions. One is add_to_eleventh which simply adds all queue elements to the eleventh queue's rear. In my opinion, it is doing what question wants.

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];
}

Thirdly, my last helper function is back_to_ints. Its purpose is take the elements in 11th queue and divide them by ten and return them in a integer array.

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;
}
}

Finally my new sorting function which is now sorts the integers in same digit. Such that, numbers[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];
}

I solved the question partially. If you want to sort the numbers in same digit, it works. Otherwise, it fails. For instance, your inputs are 112,133,122,334,345,447,346 then the result will be 112 122 133 334 345 346 447. But, if the user wants to sort something like that(111,13,12,334,345,447,1) it gives 111 1 12 13 334 345 447. So, how can I overcome this problem.

Also, I have changed my header file a bit.

#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_ */

Thank you for reopening my thread...

Answer 1

I've modified your queue a bit. To better understand the code, I use front and rear as global variables.

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 */

So the operation of adding to queue becomes

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;
}

And add an operation of deleting from a queue(return the data as well)

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;
}

So now we can implement the radix sort. It may be easier to move your data into queue with the actual numbers rather than a single digit. Note that the 11th queue is not needed if you can modify your test array *arr, and your radix_sort function could be like this:

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;
                        }
                }
        }
}

And finally you can test by calling radix_sort(your_array, your_array_size), the full code is

#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;
}

and the output is

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

Answer 2

Some good information here already. At a higher level it will be difficult to debug your code because it's more complex than it needs to be. Below is a different code that uses C to express the algorithm in a more idiomatic style.

The overall point is that when it comes to code, less is usually more: Simplicity is your friend. Features shown here:

1. Circular singly linked lists for queues. A queue is a pointer to the tail node of the list. With this, append and concatenate are fast constant-time operations.
2. Logical, reusable functional decomposition.
3. Only about 80 SLOC including a simple test. The sort function is 18 SLOC.
4. Lightly tested.

Here's the sort:

// 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;
}

And the rest:

#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.

A small test main:

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;
}