Hey everyone, I'm trying to write my first radix sorting algorithm, but have run into a problem - and my mind is too fried to think of what it is at the moment! It sorts the ones digits just fine, but after that things get mixed up. Heres the code and the output - as for me I'm taking a break for two hours or so and coming back with a fresh mind and hopefully solve it!
Code:
void displayVec(vector<int>&);
vector<int> radixSorter(vector<int>&, int);
int main()
{
srand(time(NULL));
vector<int> vec;
for (int x=0; x<10; x++)
vec.push_back(rand()%10000);
displayVec(vec);
for (int mult=1; mult<=10000; mult*=10)
vec=radixSorter(vec, mult);
displayVec(vec);
return 0;
}
void displayVec(vector<int>& vec)
{
for (int x=0; x<vec.size(); x++)
cout<<vec[x]<<" ";
cout<<endl<<endl;
}
vector<int> radixSorter(vector<int>& vec, int mult)
{
vector<int> numberSpot;
vector<int> sortedVec;
int x=0;
for (x=0; x<20; x++)
numberSpot.push_back(0);
for (x=0; x<vec.size(); x++)
{
sortedVec.push_back(0);
numberSpot[(vec[x]/mult)%10]++;
}
for (x=0; x<numberSpot.size()-1; x++)
{
numberSpot[x+1]+=numberSpot[x];
}
for (x=0; x<vec.size(); x++)
{
sortedVec[numberSpot[(vec[x]/mult)%10]-1]=vec[x];
numberSpot[(vec[x]/mult)%10]--;
}
displayVec(sortedVec);
return sortedVec;
}
output:
Code:
5329 7787 2571 7087 8356 1590 545 2620 3989 5152
2620 1590 2571 5152 545 8356 7087 7787 3989 5329
5329 2620 545 8356 5152 2571 3989 7787 7087 1590
7087 5152 8356 5329 1590 2571 545 2620 7787 3989
545 1590 2620 2571 3989 5329 5152 7787 7087 8356
8356 7087 7787 5152 5329 3989 2571 2620 1590 545
8356 7087 7787 5152 5329 3989 2571 2620 1590 545
The numbers should have been in increasing order at the end!