al__nasim

radix sort

Jun 12th, 2016
109
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.97 KB | None | 0 0
  1. #include <stdio.h>
  2. #define size 1000
  3. #include<math.h>
  4.  
  5. int b[size], c[size], d[size];
  6. void countsort(int a[], int n, int x)
  7. {
  8. int i,j, digit;
  9.  
  10. for(i=0; i<=n; i++)
  11. {
  12. c[i] = 0;
  13. }
  14.  
  15. for(i=1; i<=n; i++)
  16. {
  17. digit = a[i]/(pow(10,x-1));
  18. d[i] = digit%10;
  19. }
  20.  
  21. for(j = 1;j<=n;++j)
  22. {
  23. c[d[j]] = c[d[j]] + 1;
  24. }
  25. for(i =1;i<=n;i++)
  26. {
  27. c[i] = c[i] + c[i-1];
  28. }
  29. for(j=n; j>= 1; j--)
  30. {
  31. b[c[d[j]]] = a[j];
  32. c[d[j]] = c[d[j]] -1;
  33. }
  34. for(i=1;i<=n;i++)
  35. {
  36. a[i] = b[i];
  37. }
  38. }
  39.  
  40. void radixsort(int a[], int n,int x)
  41. {
  42. int i;
  43. for( i =1;i<=x;i++)
  44. {
  45. countsort(a,n,i);
  46. }
  47.  
  48. }
  49.  
  50. int main()
  51. {
  52. int i , n ;
  53. scanf("%d",&n) ;
  54. int a[n];
  55. for(i=1 ; i<=n ; i++)
  56. {
  57. scanf("%d",&a[i]);
  58. }
  59.  
  60. radixsort(a,n,3);
  61.  
  62. for(i = 1 ; i <=n ; i++)
  63. {
  64. printf("%d ",a[i]);
  65. }
  66.  
  67. return 0;
  68. }
Advertisement
Add Comment
Please, Sign In to add comment