C-basic/Radix.cpp at master · nafiurrashid/C-basic · GitHub

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
#include<bits/stdc++.h>
#include<time.h>
#include<math.h>
#include<algorithm>
using namespace std;

int K[500002],A[500002],C[500001],digit[500005];

int COUNTING_SORT(int*A,int d)
{
    int C[10]={0},i,j;

for(i=1;i<=500000;i++)
    {
        digit[i]= (int)(A[i]/pow(10,d-1))%10;
        C[digit[i]]++;
    }


    for(i=0;i<=9;i++)
    {
        C[i+1]=C[i]+C[i+1];
    }

    for(j=500000;j>=0;j--)
    {


         K[C[digit[j]]] = A[j];
        C[digit[j]] = C[digit[j]]-1;

    }
    for(i=1;i<=500000;i++)
    {
        A[i]=K[i];
    }


}


int RADIX_SORT(int*A,int d)
{
    int i;

    for(i=1;i<=d;i++)
    {
        COUNTING_SORT(A,i);

    }


}

int main()
{
     int i;
    srand(time(NULL));
    for(i=0;i<500000;i++)
    {
        A[i]=rand()%100;

    }


         long start= clock();
        RADIX_SORT(A,2);
       long end = clock();
       int difference = end -start;
      int seconds = (difference*1.0)/CLOCKS_PER_SEC;
      printf("%lf \n",seconds);

      }