In this tutorial you will learn about radix sort program in C.
Radix sorting technique is one of the oldest techniques of sorting.
Lets assume that we are given a list of some names and asked to sort them alphabetically. We would normally proceed by first dividing the names into 26 different sets (since, there are total of 26 alphabets) with each set containing names that start with the same alphabet. In the first set, we will put all the names which start with alphabet ‘A’. In the Second Set, we will put all the names that start with ‘B’ and so on.
Also Read: Quick Sort in C [Program & Algorithm]
After this comparison of the first alphabets of all the names, each set is further divided into different sub-sets according to the second alphabet of the names.
This process continues till the list becomes completely sorted.
However, the drawback of radix sorting technique is that we have to keep track of lots of sets and its sub-sets simultaneously.
To ease out on this drawback, there are two methods available in radix sorting:
1. Most Significant Digit Radix Sort (MSD)
2. Least Significant Digit Radix Sort (LSD)
In least significant digit radix sort, sorting is performed digit by digit starting from the least significant digit and ending at the most significant digit.
The concept of most significant sorting is to divide all the digits with an equal value into their own set and then do the same thing with all the sets until all of them are sorted.
Analysis of Radix Sort ALgorithm
The number of passes p is equal to the number of digits in largest element and in every pass (iteration) we have n operations where n is the total number of elements. In this program we can see that the outer loop iterates p times and inner loop iterates n times. Hence, run time complexity of radix sort is denoted by O(p*n).
If the number of digits in largest element is equal to n, then the run time becomes O(n square) which is the worst case scenario in radix sort. The best case scenario of radix sort is if the number of digits in largest element is Log n. In this case, the run time becomes O(n log n).
The major disadvantage of radix sort is the need for extra memory for maintaining Queues and hence it is not an in-place sort. It is therefore a stable sort.
Radix Sort Program in C
|
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 |
#include<stdio.h> #include<stdlib.h> struct node { int data ; struct node *next; }*start=NULL; void radix_sorting(); int larger_dig(); int digit(int num, int k); main() { struct node *temp,*q; int count,n,num_item; printf("Enter the Number of Elements to be Inserted into the List : "); scanf("%d", &n); for(count=0;count<n;count++) { printf("Enter element %d : ",count+1); scanf("%d",&num_item); temp= malloc(sizeof(struct node)); temp->data=num_item; temp->next=NULL; if(start==NULL) start=temp; else { q=start; while(q->next!=NULL) q=q->next; q->next=temp; } } radix_sorting(); printf("Sorted List is :\n"); q=start; while( q !=NULL) { printf("%d ", q->data); q = q->next; } printf("\n"); } void radix_sorting() { int count,k,dig,least_sig,most_sig; struct node *p, *rear[10], *front[10]; least_sig=1; most_sig=larger_dig(start); for(k=least_sig; k<=most_sig; k++) { for(count=0; count<=9 ; count++) { rear[count] = NULL; front[count] = NULL ; } for( p=start; p!=NULL; p=p->next ) { dig = digit(p->data, k); if(front[dig] == NULL) front[dig] = p ; else rear[dig]->next = p; rear[dig] = p; } count=0; while(front[count] == NULL) count++; start = front[count]; while(count<9) { if(rear[count+1]!=NULL) rear[count]->next=front[count+1]; else rear[count+1]=rear[count]; count++; } rear[9]->next=NULL; } } int larger_dig() { struct node *p=start; int large=0,ndigit=0; while(p != NULL) { if(p ->data > large) large = p->data; p = p->next ; } while(large != 0) { ndigit++; large = large/10 ; } return(ndigit); } int digit(int num, int k) { int digit, count ; for(count=1; count<=k; count++) { digit = num % 10 ; num = num /10 ; } return(digit); } |
Output
If you found anything incorrect or have doubts regarding above radix sort program in C then comment below.
