Radix Sorting with using queue

Question 1

Radix Sorting with using queue

c linked-list queue radix-sort

mustafaSarialp · Oct 5, 2012 · Viewed 7.2k times · Source

Answer

Answer

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

Question 2

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

Radix Sorting with using queue

Answer

Related questions