Radix sorting

This is a discussion on Radix sorting within the C++ Programming forums, part of the General Programming Boards category; Hey everyone, I'm trying to write my first radix sorting algorithm, but have run into a problem - and my ...

  1. #1
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728

    Radix sorting

    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!

  2. #2
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    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.
    Code:
    // 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]]--;
    	}
        }
    }

  3. #3
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help with linked list sorting function
    By Jaggid1x in forum C Programming
    Replies: 6
    Last Post: 06-02-2009, 03:14 AM
  2. My own itoa()
    By maxorator in forum C++ Programming
    Replies: 18
    Last Post: 10-15-2006, 12:49 PM
  3. Radix Sorting Help
    By wvu2005 in forum C Programming
    Replies: 10
    Last Post: 10-29-2005, 07:15 PM
  4. radix sort and radix exchange sort.
    By whatman in forum C Programming
    Replies: 1
    Last Post: 07-31-2003, 01:24 PM
  5. Still Needing Help : selection sorting
    By Unregistered in forum C Programming
    Replies: 6
    Last Post: 10-14-2001, 09:41 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21