Sorting/radixSort.cpp at master · avani112/Sorting · 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
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 <iostream>
#include <string>

using namespace std ;

class queue{
 public :   int front = 0 ;
            int rear = -1 ;
            int arr[10] ;
            int size ;
            int filled = 0 ;

     queue(){
          size = 10 ;
     }

     void enqueue(int x){
          if(filled == size){
               cout << "Queue exced the size " <<endl;
          }
          else{
               if(rear==size-1){
                    rear = 0 ;
                    arr[rear] = x ;

               }else
                  arr[++rear] = x ;
               ++filled ;
          }
     }
     int dequeue(){

          if(filled == 0) {
               cout << "Empty Queue" << endl;
               return -1 ;
          }else {

               int rvalue = arr[front] ;
               if(front == size-1){
                     front = 0 ;
                     filled-- ;
               }
               else{
                  front++ ;
                  filled-- ;
               }
               return rvalue ;
          }
     }
     int returnSize(){
          return size ;
     }

     bool isEmpty(){
          if (filled == 0)
             return true ;
          else
             return false ;

     }
};


int getDigit(int a , int num){
     int divider = 1 ;
     --a ;
     while(a--){
          divider = divider * 10 ;
     }
     int digit = num / divider % 10 ;
     return digit ;
}


int getMax(int a[]){
     int largest = a[0] ;
     for(int i=1 ; i<10 ; ++i){
          if(a[i] > largest){
               largest = a[i];
          }
     }
     return largest ;
}

int lengthOfInt(int x){
     int length = 0 ;
     while(x!=0){
          x /= 10 ;
          ++length ;
     }
     return length ;
}

void printArray(int a[] , int len){
     for(int i=0; i<len ; ++i){
          cout << a[i] << " , " ;
     }
}


int main(){
     int lengthOfArray = 10 ;
     int a[10] = {458,4449,966,558,62454,244,145,28854,636,447} ;
     int length = lengthOfInt(getMax(a)) ;
     queue q[10] ;


     for(int i=1 ; i<=length ; ++i){

           for(int j=0 ; j<lengthOfArray ; ++j){

                int k  = getDigit(i,a[j]) ;
               q[k].enqueue(a[j]) ;

           }
           int j=0 ;
           for(int k=0 ; k<10 ; ++k){
                while(q[k].filled > 0) {
                     a[j++] = q[k].dequeue() ;
                }
           }
     }
     printArray(a , 10) ;

     return 0 ;
}