I have implemented radix and counting sorts in this program where i take inputs as the number of the numbers you want to sort and the number of digits(at max).
Then the numbers, which will be sorted, are taken as random and sorted according to the corresponding algorithm.
Take a look at the C-Code.
Radix and Counting Sort
- #include<stdio.h>
- #include<time.h>
- #include<stdlib.h>
- #include<math.h>
- void count_sort(int num[],int sortd[],int no,int rng);
- void show(int inp[],int no);
- void radixsort(int a[],int n,int d);
- int cnt_rdx=0,cnt_cntsrt=0;
- int main()
- {
- int no,i,digt,rng;
- int *num,*cnt_srt_num;
- printf("\nHow many Numbers you want to sort:- ");
- scanf("%d",&no);
- printf("\nWhat is the Number of Digits(at max) in a number:- ");
- scanf("%d",&digt);
- rng=pow(10,digt);
- num=(int *)calloc(no,sizeof(int));
- cnt_srt_num=(int *)calloc(no,sizeof(int));
- srand(time(0));
- for(i=0;i<no;i++)
- num[i]=rand()%rng;
- printf("\nThe Unsorted Numbers are:");
- show(num,no);
- count_sort(num,cnt_srt_num,no,pow(10,digt));
- printf("\nThe Counting Sorted Numbers are:");
- show(cnt_srt_num,no);
- printf("Time Complexity : %d\n",cnt_rdx);
- radixsort(num,no,digt);
- printf("\nThe Radix Sorted Numbers are:");
- show(num,no);
- printf("Time Complexity : %d\n",cnt_cntsrt);
- getch();
- return 0;
- }
- void count_sort(int num[],int sortd[],int no,int rng)
- {
- int i;
- int *indx_num;
- indx_num=(int *)calloc(rng,sizeof(int));
- for(i=0;i<no;i++)
- indx_num[num[i]]++;
- for(i=1;i<rng;i++)
- indx_num[i]=indx_num[i]+indx_num[i-1];
- for(i=no-1;i>=0;i--)
- {
- cnt_rdx++;
- sortd[indx_num[num[i]]-1]=num[i];
- indx_num[num[i]]--;
- }
- }
- void show(int inp[],int no)
- {
- int i;
- for(i=0;i<no;i++)
- printf(" %d",inp[i]);
- printf("\n");
- }
- void radixsort(int a[],int n,int d)
- {
- int end[10],start[10],first,p,q,exp,k,i,y,j;
- struct nd
- {
- int info;
- int next;
- };
- struct nd *node;
- node=(struct nd *)malloc(n*sizeof(struct nd));
- for(i=0;i<n-1;i++)
- {
- node[i].info=a[i];
- node[i].next=i+1;
- }
- node[n-1].info=a[n-1];
- node[n-1].next=-1;
- first=0;
- for(k=1;k<=d;k++) //consider 3 digit number
- {
- for(i=0;i<10;i++)
- {
- start[i]=-1;
- end[i]=-1;
- }
- while(first!=-1)
- {
- cnt_cntsrt++;
- p=first;
- first=node[first].next;
- y=node[p].info;
- exp=pow(10,k-1);
- j=(y/exp)%10;
- q=end[j];
- if(q==-1)
- start[j]=p;
- else
- node[q].next=p;
- end[j]=p;
- }
- for(j=0;j<10&&start[j]==-1;j++)
- ;
- first=start[j];
- while(j<=9)
- {
- for(i=j+1;i<10&&start[i]==-1;i++)
- ;
- if(i<=9)
- {
- p=i;
- node[end[j]].next=start[i];
- }
- j=i;
- }
- node[end[p]].next=-1;
- }
- //copy into original array
- for(i=0;i<n;i++)
- {
- a[i]=node[first].info;
- first=node[first].next;
- }
- /*printf("Sorted Data:\n");
- for(i=0;i<n;i++)
- printf("%d. %d\n",i+1,a[i]);*/
- }
- /*void radixsort(int a[],int n)
- {
- int i,b[MAX],m=0,exp=1;
- int bucket[10]={0};
- for(i=0;i<n;i++)
- {
- if(a[i]>m)
- m=a[i];
- }
- while(m/exp>0)
- {
- for(i=0;i<n;i++)
- bucket[a[i]/exp%10]++;
- for(i=1;i<10;i++)
- bucket[i]+=bucket[i-1];
- for(i=n-1;i>=0;i--)
- b[--bucket[a[i]/exp%10]]=a[i];
- for(i=0;i<n;i++)
- a[i]=b[i];
- exp*=10;
- #ifdef SHOWPASS
- printf("\nPASS : ");
- print(a,n);
- #endif
- }
- }*/
Discussions will be carried out later,if needed. Any suggestions are highly solicited.
Thank You.
