NightRaven97

Radix Sort using stack

May 4th, 2016
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.77 KB | None | 0 0
  1. //Radix Sort
  2. #include<stdio.h>
  3. #include<math.h>
  4. #define MAX_SIZE 20
  5. int arr[MAX_SIZE],n,s0[MAX_SIZE],s1[MAX_SIZE],s2[MAX_SIZE],s3[MAX_SIZE],s4[MAX_SIZE],s5[MAX_SIZE],s6[MAX_SIZE],s7[MAX_SIZE],s8[MAX_SIZE],s9[MAX_SIZE],top[]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},pos=0;
  6. int findMaxDig()
  7. {
  8.     int i,max=0,temp,count;
  9.     for(i=0;i<n;i++)
  10.     {
  11.         count=0;
  12.         temp=arr[i];
  13.         while(temp>0)
  14.         {
  15.             count++;
  16.             temp/=10;
  17.         }
  18.         if(count>max)
  19.             max=count;
  20.     }
  21.     return max;
  22. }
  23. void push(int s[MAX_SIZE],int t, int ele)
  24. {
  25.     s[++top[t]]=ele;
  26. }
  27. void pop(int s[MAX_SIZE],int t)
  28. {
  29.     int i;
  30.     for(i=0;i<=top[t];i++)
  31.     {
  32.         arr[pos++]=s[i];
  33.     }
  34. }
  35. radixSort(int maxDig)
  36. {
  37.     int i,j,k,place,extr,dig;
  38.     for(i=1;i<=maxDig;i++) //MaxDig num of passes
  39.     {
  40.         place=pow(10,i);
  41.         extr=pow(10,i-1);
  42.         for(j=0;j<n;j++) //n elements
  43.         {
  44.             dig=arr[j]%place;
  45.             dig/=extr;
  46.             switch(dig)
  47.             {
  48.                 case 0:
  49.                     push(s0,0,arr[j]);
  50.                     break;
  51.                 case 1:
  52.                     push(s1,1,arr[j]);
  53.                     break;
  54.                 case 2:
  55.                     push(s2,2,arr[j]);
  56.                     break;
  57.                 case 3:
  58.                     push(s3,3,arr[j]);
  59.                     break;
  60.                 case 4:
  61.                     push(s4,4,arr[j]);
  62.                     break;
  63.                 case 5:
  64.                     push(s5,5,arr[j]);
  65.                     break;
  66.                 case 6:
  67.                     push(s6,6,arr[j]);
  68.                     break;
  69.                 case 7:
  70.                     push(s7,7,arr[j]);
  71.                     break;
  72.                 case 8:
  73.                     push(s8,8,arr[j]);
  74.                     break;
  75.                 case 9:
  76.                     push(s9,9,arr[j]);
  77.                     break;
  78.             }
  79.         }
  80.         pop(s0,0);
  81.         pop(s1,1);
  82.         pop(s2,2);
  83.         pop(s3,3);
  84.         pop(s4,4);
  85.         pop(s5,5);
  86.         pop(s6,6);
  87.         pop(s7,7);
  88.         pop(s8,8);
  89.         pop(s9,9);
  90.         for(k=0;k<10;k++)
  91.             top[k]=-1;
  92.         pos=0;
  93.     }
  94. }
  95. void main()
  96. {
  97.     int i;
  98.     printf("Enter the number of elements:");
  99.     scanf("%d",&n);
  100.     for(i=0;i<n;i++)
  101.         scanf("%d",&arr[i]);
  102.     radixSort(findMaxDig());
  103.     for(i=0;i<n;i++)
  104.     {
  105.         printf("%d\t",arr[i]);
  106.     }
  107. }
Add Comment
Please, Sign In to add comment