Sort Radix Using Queue

Question

I wanted to create a sortix implementation using queues.

I could not understand what part of my code has problems or which resources I should read. My code may be completely wrong, but this is my implementation without any help (I have not yet studied the data structure and algorithms).

I created a function, but it did not work. During the research, I saw some code examples, but they seemed more complicated to me.

First, I wanted to find the least significant digit of all integers. Then sort them in the queue element whose index matches , then after sorting, copy all the queues to the end of the 11th element of the queue. Make this type in the 11th element of the queue until the most significant digit is reached.

I could find the least significant figure. And sort by that number. But I could not analyze other numbers. For example; I could sort 1, 2, 4, 5, 3, but when it comes time to sort 2 or more digits, it fails ...

I hope I understood and briefly explained my problem.

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

Change 1 (some progress has been made)

I followed William Morris's suggestions. I had to ask the same question in CodeReview, and he gave me some instructions to make my code more clear.

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

First, I created the add_to_q function, which adds a value to the associated queue, and this helped get rid of code duplication. By the way, James Howry’s path is simple, but he uses recursion again.

 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 of them is add_to_eleventh, which simply adds all the elements of the queue to the eleventh queue of the queue. In my opinion, he does what he 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 to take elements in the 11th queue and divide them into ten and return them to an 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 sort function, which now sorts integers in the same digit. Thus, the 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 issue partially. If you want to sort numbers in the same digit, this works. Otherwise, it fails. For example, 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 this (111,13,12,334,345,447,1), he gives 111 1 12 13 334 345 447 . So how can I solve this problem.

In addition, I slightly changed my header file.

 #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 opening my topic ...

Answer 1

I changed your lineup a bit. To better understand the code, I use front and back 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 queue operation 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 a delete operation from the queue (also return data)

 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 radix sorting. It may be easier to move your data into a queue with actual numbers, rather than a single digit. Note that the 11th queue is not needed if you can change your test array * arr, and your radix_sort function might 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

 #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 way out is

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

Answer 2

Some useful information is already here. At a higher level, it will be difficult for you to debug your code, because it is more complex than it should be. Below is another code that uses C to express the algorithm in a more idiomatic style.

The common point is that when it comes to code, less is usually more: simplicity is your friend. Functions shown here:

• Circular single lists for queues. A queue is a pointer to the tail of a node in a list. At the same time, addition and concatenation are fast operations with constant time.
• Logical, reusable functional decomposition.
• Only about 80 SLOC, including a simple test. The sorting function is 18 SLOC.
• Easily tested.

Here's the sorting:

 // 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 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 basic check:

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

Answer 3

Disclaimer: I did not implement radix sorting before or did not check the code below. I will leave it to you as an exercise.

When you find yourself copying something more than once, stop and think: there should be a template.

Your switch statement is a lot of copies. In case 1: you have a line:

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

I guess this should be:

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

If you reinstalled this code, maybe it was easier for you to see it?

How about replacing the entire switch statement:

 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 4

The problem that I saw in the first code example is that

curNum = curNodep-> element.key

curNum always has a full number, and the switch statement always does curNum% 10 , and this is just a test of the last digit.

In a recursive solution (recursion is not a problem) you need to pass a parameter to find out which digit should deal.

I know this technique as immersion.

If you see the samples that you put at the end of the answer, you can see that the last digit is the customer, you can change the input samples to better see this. Add large numbers with a small last number, for example, "901", see Result.

Sorry for my English...