C Program To Implement Radix Sort Algorithm
Learn How To Implement Radix Sort Algorithm in C Programming Language. This algorithm for Radix Sort in C Programming is performed using Linked List. The Radix Sort in Data Structure can be alternatively performed using Arrays as well.
What is Radix Sort Algorithm?
The Radix Algorithm was previously used to sort punch cards in the olden days. The sorting starts from the least significant digit and goes upto the most significant digit. Therefore, there are two different methods used for Radix Sort which are listed below.
- Least Significant Digit Radix Sort (LSD)
- Most Significant Digit Radix Sort (MSD)
C Program For Radix Sort Algorithm using Linked List
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 | #include<stdio.h> #include<stdlib.h> struct node { int data; struct node *link; }; struct node *start = NULL; void radix_sort(); int larger_digit(); int digit_finder(int number, int k); int main() { struct node *temp, *x; int count, limit, element; printf("\nEnter Total Number of Elements:\t"); scanf("%d", &limit); for(count = 0; count < limit; count++) { printf("Element No. %d:\t", count + 1); scanf("%d", &element); temp = malloc(sizeof(struct node)); temp->data = element; temp->link = NULL; if(start == NULL) { start = temp; } else { x = start; while(x->link != NULL) { x = x->link; } x->link = temp; } } radix_sort(); printf("\nSorted List\n"); x = start; while(x != NULL) { printf("%3d", x->data); x = x->link; } printf("\n"); return 0; } void radix_sort() { int count, k, digit, least_significant, most_significant; struct node *rear[10], *front[10], *p; least_significant = 1; most_significant = larger_digit(start); for(k = least_significant; k <= most_significant; k++) { for(count = 0; count <= 9; count++) { rear[count] = NULL; front[count] = NULL ; } for(p = start; p != NULL; p = p->link) { digit = digit_finder(p->data, k); if(front[digit] == NULL) { front[digit] = p; } else { rear[digit]->link = p; } rear[digit] = p; } count = 0; while(front[count] == NULL) { count++; } start = front[count]; while(count < 9) { if(rear[count + 1] != NULL) { rear[count]->link = front[count + 1]; } else { rear[count + 1] = rear[count]; } count++; } rear[9]->link = NULL; } } int larger_digit() { struct node *p = start; int temp = 0, digit = 0; while(p != NULL) { if(p ->data > temp) { temp = p->data; } p = p->link ; } while(temp != 0) { digit++; temp = temp / 10; } return(digit); } int digit_finder(int number, int k) { int term, count; for(count = 1; count <= k; count++) { term = number % 10; number = number / 10; } return(term); } |
Radix Sort Algorithm Analysis
The run time complexity of the radix sorting algorithm is O(p * n) where p is the number of iterations of the outer loop and n is the number of iterations of the inner loop. The worst case scenario complexity of this algorithm is O(n) whereas the best case scenario complexity is O(n log n).
Radix Sort is a stable sort and is also an in-place sort. However, this algorithm takes extra space for maintaining queue overheads. This algorithm is preferable when the number of digits are small.
Output
If you have any compilation errors or doubts about Radix Sort Algorithm in C Programming, let us know about it in the comment section below.
Is Radix Sort Algorithm, the fastest algorithm for sorting array elements?
Radix sort method is not the fastest. There are many better algorithms than this such as Heap Sort, Quick Sort, etc.
Can you explain more about LSD Radix Sort and Most Significant Radix Sort? I have never heard of it before.
Hi Nishit. There is a drawback with Radix Sorting. We need to keep track of nunerous sets and sets which is a very memory intensive task. To overcome this drawback, the LSD Radix and MSD Radix methods can be used.
This code is too difficult to grasp. Bubble sort is much easier. 😀
I need the Radix Sort Algorithm Animation. Where can I get it?
Even though the Radix Sort Algorithm executes in O(n) time, they do not have much practical applications due to certain limitations that they possess such as Range of Input, Uniform distribution and Integer Data as the input.
thank you Tushar for this wonderful turorial. But I got a question: in the conclusion, you said “The worst case scenario complexity of this algorithm is O(n) whereas the best case scenario complexity is O(n log n).”
However, clearly O(n) grows slower than O(n log n), is that a typo? or I misunderstood.