Radix Sort Without Queues/Vectors

novablows (35)
I need help implementing the next step of Radix Sort. As of now, I have every individual digit for every number. The next step would be placing each digit (0-9) into its own corresponding bin. I'm kind of confused how to do this and I've been working on this for a while and still can't figure it out. 

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
 
#include <iostream>
#include <ctime>
#include <cstdlib>
#include <cmath>
using namespace std;
int i;

long signed int findmax(long signed int a,long signed int b){
return a>b ? a : b;}

void radixsort(int p[], int n){
int max,b[n],exp=1;
	
	    for(i=0;i<n;i++)
            if (i==0) max=p[i];
		else
		max=findmax(p[i],max);

		while(max/exp>0){
		for(i=0;i<n;i++){
	    b[i]=abs((p[i]/exp)%10);	
		cout<<b[i]<<" ";
		}
		exp*=10;
		} 

}



int main(){
int n=20;
int p[n];
srand((unsigned)time(0));
for(i=0;i<n;i++)
p[i]=rand()%20+0;
for(i=0;i<n;i++)
cout<<p[i]<<" ";
cout<<endl;
radixsort(p,n);
for(i=0;i<n;i++){}  //ignore this for now
}


Do I have to make 10 seperate arrays for each digit?
novablows (35)
Ok I'm trying to sort the units digit, and it works for half the array size, but I can't figure out how to fix it..

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
 
#include <iostream>
#include <ctime>
#include <cstdlib>
#include <cmath>
using namespace std;
int i;

long signed int findmax(long signed int a,long signed int b){
return a>b ? a : b;}

void radixsort(int p[], int n){
int max,b[n],exp=1;
	
	    for(i=0;i<n;i++)
        if (i==0) max=p[i];
		else
		max=findmax(p[i],max);

		while(max/exp>0){
		for(i=0;i<n;i++){
	    b[i]=abs((p[i]/exp)%10);
		}
		int digit=0,k=0;
        while(digit<10){
		for(i=0;i<n;i++){
		if(b[i]==digit)
		b[k++]=p[i];
		}
		digit++;
		}
		for(k=0;k<n;k++)
		cout<<b[k]<<" ";
		exp*=10;
		}       

}

int main(){
int n=10;
int p[n];
srand((unsigned)time(0));
for(i=0;i<n;i++)
p[i]=rand()%9+0;
for(i=0;i<n;i++)
cout<<p[i]<<" ";
cout<<endl;
radixsort(p,n);
for(i=0;i<n;i++){}
}


output:

0 0 8 2 8 2 0 4 5 0
0 0 0 0 2 4 5 4 5 0
Last edited on
novablows (35)
Thanks for the help guys!... But I just got it for negatives and positives. 1.2 million long signed ints with a run time of 1.3 seconds.
Topic archived. No new replies allowed.