Radix sorting

[PJYelton]

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!

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:

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!

[Nick]

The sort used to sort the digits must be stable. By
that I mean if your sorting
A = {101, 232, 204, 444} with respect to the second digit you
must bet
A = {101, 204, 232, 444} not
A = {204, 101, 232, 444}.

This is an example of a stable sort. If you modify
it to sort a specific digit it should work.

// sorts A[0..n-1] into C[0..n-1]
// B[0..k] is a temporary array
void counting_sort(int A[], int B[], int C[], int n, int k)
{
    for (int i = 0; i <= k; ++i)
	B[i] = 0;

    for (int i = 0; i < n; ++i) 
	B[A[i]]++;
    
    for (int i = 1; i <= k; ++i)
	B[i] += B[i - 1];

    for (int i = n - 1; i >= 0; --i) {
	C[B[A[i]] - 1] = A[i];
	if (B[A[i]] > 0) {
	    B[A[i]]--;
	}
    }
}

[PJYelton]

Yep, thanks! It came to me what my error was as soon as I turned my computer back on - my last for loop needs to run backwards, not forwards, so as to remain stable like you said. Works like a charm now!