Tell me more ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 1 down vote favorite

I have been trying to finish a book, Problem Solving and Program Design in C. In that book, there is a chapter, Dynamic Data Structures. I have understood main parts of that chapter. But, I couldn't solve one of the Programming Projects.

The question simply asks me to create a radix-sort implementation by using queues in C.

And its directions for this is;

For instance we have 3 digit numbers. So, it would require 3 passes through the list. During first pass it will examine the least significant digit of all numbers and add those numbers to the rear of the queue whose array subscript matches the digit. It goes like this until reaching most significant digit. And also after each analyzing, the all queues [0 - 9] will added to rear of the 11th queue and analyzing will again happen on 11th queue, then final sorted (in ascending order) would be added to rear of 11th queue. I wanted to give a full explanation of the problem because my code is a mass.

Firstly, I tried to implement a header file which contains linked lists and function declarations:

#ifndef RADIX_H_
#define RADIX_H_

typedef struct queue_element_s {
    int key;
}queue_element_t;

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

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

queue_node_t * radixSort(const queue_node_t *arrInts, queue_t **oldQueue, int size);
int scanValues(queue_node_t *numbers);
void displayRadixed(queue_t *sorted);
#endif /* RADIX_H_ */

And my radix sort function:

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

I guess my implementation is totally wrong.

To be honest, I don't have a background or knowledge at data structures and also not a good programmer. But, I have been working on it. Like trying to improve my English.

I am waiting your suggestion how to implement it or where should I change in my function.

Thanks in advance...

share|improve this question
1  
Asking how to do stuff is off topic for this site. Best to ask this on programmers.stackexcahnge.com. There are many more people there who are very bright. and it fits better there. – Loki Astari Oct 21 '12 at 15:54
I have already asked this question on Stackoverflow. It would more appropriate in here so that they pointed here as you pointed programmers.stackexchange.com. Then, they closed thread. Now, what should I do. Should I follow your suggestion and posting same threat on programmers.stackexchange.com or deleting this threat and again posting on programmers.stackexchange.com. Or should I wait? What is your suggestion @Loki Astari – mustafaSarialp Oct 21 '12 at 22:18
@mustafaSarialp Code review if for code that you already have working. Is this code working? – James Khoury Oct 22 '12 at 3:32
@JamesKhoury I guess, no it is not... As I remember, it only handles first least significant digit and useless for rest of digits. I asked on stackoverflow but they closed thread. Also they pointed here; "This question belongs on codereview.stackexchange.com". – mustafaSarialp Oct 22 '12 at 3:53
@mustafaSarialp I voted to reopen your StackOverflow question. – James Khoury Oct 22 '12 at 4:05

closed as off topic by Corbin, James Khoury, Glenn Rogers, Jeff Vanzella, mseancole Oct 23 '12 at 15:27

Questions on Code Review Stack Exchange are expected to relate to code review request within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

1 Answer

up vote 0 down vote

Mustafa, here are some hints. I hope they help.

  1. simplify your interface. There seems no good reason why the list to sort cannot be accepted in an array, not a linked-list. The sorted list can then be returned in place - ie. in the same array. So your function looks something like:

    int radix_sort(int * arr, size_t size);

  2. notice that you have a huge amount of code duplication. That is almost always a bad sign. You should factor-out the common code.

  3. you have mixed up queue handling and radix-sorting. Write some separate functions that can handle queue creation, etc and call these functions from the sort function.

  4. you are using recursion. This is a powerful tool that is best kept until you are more proficient at C. And even then, think twice - I've been programming C for a few decades and have rarely used recursion. Use a loop instead.

  5. after each stage of the process, return the queued items to the input array in their new order. This is best understood by looking at the Wikipedia page on radix sort.

  6. don't mix naming style - use either radix_sort and queue_node_t etc, or radixSort and queueNode (and maybe drop the _t).

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.