Thread: Radix Sort

  1. #1
    Registered User
    Join Date
    Sep 2002
    Posts
    417

    Radix Sort

    All right, I've run out of time to work on this, so can someone please figure out why it isn't working right?

    Code:
    // RADIXSORT.CPP
    
    #include <math.h>
    #include "apmatrix.h"
    #include "apvector.h"
    
    int const MAX_LIST_SIZE = 100;
    
    // Function: digit
    // Computes the kth digit in number
    //
    // Inputs: integers number and k
    // Outputs: the kth digit in number
    
    int digit(int number, int k)
    {
    	return (number/int(pow(10,k-1))) % int(pow(10,k-1));
    }
    
    // Function: initializeCounters
    // Initializes all bin counters to zero
    
    void initializeCounters(apvector<int> &binCounters)
    {
    	for (int i = 0; i < binCounters.length(); i++)
    		binCounters[i] = 0;
    }
    
    // Function: addToBin
    // Insert number in bin structure, as indicated by place
    //
    // Inputs: a bin structure bins, a vector of bin counters, 
    //		   a number, and a place
    // Outputs: bin structure bins and its vector of counters
    //			have been altered to reflect addition of number
    //			in bin eindexed by place
    
    template<class element>
    void addToBin(apmatrix<element> &bins,
    			  apvector<int> &binCounters, int number, int place)
    {
    	bins[place][binCounters[place]] = number;
    }
    
    // Function: collectBins
    // Append numbers in bins to list
    //
    // Inputs: list, a bin structure, and a vector of the counters for the
    //			bin structure
    // Outputs: a list
    
    template<class element>
    void collectBins(apvector<element> &list, apmatrix<element> &bins, 
    				 apvector<int> &binCounters)
    {
    	//put everything back in one list
    	//matrix[row][column];
    	int row = 0;
    	int col = 0;
    	for (int i=0; i<list.length(); i++)
    	{
    		//if (bins[row][col] < binCounters[row])
    		//if (col < binCounters[row])
    		if (binCounters[row] > 0/* && col < binCounters[row]*/)
    		{
    			list[i] = bins[row][col];
    			if (col < bins[row].length())
    				col++;
    		}
    		else if (col == bins.numcols())
    		{
    			col = 0;
    			//cout << row << " " << col << endl;
    			if (row+1 < bins.numrows())
    				row++;
    		}
    	}
    }
    
    // Function: radixSort
    // Sorts numbers in list into ascending order
    //
    // Inputs: list and its length
    // Outputs: the list with numbers sorted in ascending order
    
    template<class element>
    void radixSort(apvector<element> &list, int n)
    {
    	int j, k;
    	apmatrix<element> bins(10,MAX_LIST_SIZE);
    	apvector<int> binCounters(10);
    
    	initializeCounters(binCounters);
    
    	// For k loop controls digit used to classify data.
    	for (k = 1; k <= 4; k++)
    	{
    		// For j loop iterates through all numbers, putting them into
    		// bin determined by kth digit.
    		for (j = 0; j < n; j++)
    			addToBin (bins, binCounters, list[j], digit(list[j], k));
    		collectBins (list, bins, binCounters);
    		initializeCounters(binCounters);
    	}
    }

  2. #2
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,981
    First off, are you sure apmatrix and apvector are implemented correctly?
    Looking over the posted code now....

    gg

  3. #3
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    I think you need to add:
    Code:
    ++binCounters[place];
    after
    Code:
    bins[place][binCounters[place]] = number;
    Otherwise you will keep writing over the zero spot in your bins.

  4. #4
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,981
    Your digit function doesn't work; digit(1234,1) should return 4 right? If so, you can try this (non-elegant) implementation in its place until you work out a math based solution - or use this as is:

    Code:
    int digit(int number, int k)
    {
        static char str[25];
        sprintf(str,"%d",number);
        int pos = strlen(str) - k; //k should not be 0
        if (pos >= 0)
            return str[pos] - '0';
        return 0;
    }
    gg

  5. #5
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    The digit function is close, just change it to:
    Code:
    return (number/int(pow(10,k-1))) % 10;
    and it should work.

  6. #6
    Registered User
    Join Date
    Sep 2002
    Posts
    417
    Originally posted by PJYelton
    The digit function is close, just change it to:
    Code:
    return (number/int(pow(10,k-1))) % 10;
    and it should work.
    Work it out on paper:

    If you have 1234:

    number/int(pow(10,k-1))) % int(pow(10,k-1));

    so:

    (1234/10^(k-1)) % 10^(k-1)

    if you want the 3... you use 2 as k

    if you divide 1234 by 10 (10^1), its an int so it ends up as 123.

    123 modulus 10 is the remainder of 123/10... thats 3

    [EDIT]All right... I was wrong. Your way cuts off the leading digits, mine doesn't. It works sometimes on mine apparently. It works with 1 or 2.[/EDIT]

  7. #7
    Registered User
    Join Date
    Sep 2002
    Posts
    417
    Originally posted by PJYelton
    I think you need to add:
    Code:
    ++binCounters[place];
    after
    Code:
    bins[place][binCounters[place]] = number;
    Otherwise you will keep writing over the zero spot in your bins.
    I tried using that and it gives another illegal index.

    By the way, I've tested it and using
    ++i is SLOWER than using i++ by a tiny amount. So if you need a speedier program, use i++

  8. #8
    Registered User
    Join Date
    Sep 2002
    Posts
    417
    Reverse sorting...

    There's the code... if you passed an array with all the integers 0 through 9 (In a random order), you'd end up sorted like this:

    9
    8
    7
    6
    5
    4
    3
    2
    1
    0

    Also, if the collectBins() function is commented out, the program seems to function exactly the same, even though list isn't changed in any function but collectBins!

    [EDIT]All right, the problem is in the addToBin() function... it is supposed to modify the bin counters, but it isn't. I tried incrementing the bincounter[place] like mentioned above, but that gave vector index problems

    Code:
    // RADIXSORT.CPP
    
    #include <math.h>
    #include "apmatrix.h"
    #include "apvector.h"
    
    int const MAX_LIST_SIZE = 100;
    
    // Function: digit
    // Computes the kth digit in number
    //
    // Inputs: integers number and k
    // Outputs: the kth digit in number
    
    int digit(int number, int k)
    {
    	return (number/int(pow(10,k-1))) % 10;
    }
    
    // Function: initializeCounters
    // Initializes all bin counters to zero
    
    void initializeCounters(apvector<int> &binCounters)
    {
    	for (int i = 0; i < binCounters.length(); i++)
    		binCounters[i] = 0;
    }
    
    // Function: addToBin
    // Insert number in bin structure, as indicated by place
    //
    // Inputs: a bin structure bins, a vector of bin counters, 
    //		   a number, and a place
    // Outputs: bin structure bins and its vector of counters
    //			have been altered to reflect addition of number
    //			in bin eindexed by place
    
    template<class element>
    void addToBin(apmatrix<element> &bins,
    			  apvector<int> &binCounters, int number, int place)
    {
    	bins[place][binCounters[place]] = number;
    }
    
    // Function: collectBins
    // Append numbers in bins to list
    //
    // Inputs: list, a bin structure, and a vector of the counters for the
    //			bin structure
    // Outputs: a list
    
    template<class element>
    void collectBins(apvector<element> &list, apmatrix<element> &bins, 
    				 apvector<int> &binCounters)
    {
    	//put everything back in one list
    	//matrix[row][column];
    	int row = 0;
    	int col = 0;
    	for (int i=0; i<list.length(); i++)
    	{
    		//if (bins[row][col] < binCounters[row])
    		//if (col < binCounters[row])
    		if (binCounters[row] > 0/* && col < binCounters[row]*/)
    		{
    			list[i] = bins[row][col];
    			if (col < bins[row].length())
    				col++;
    		}
    		else if (col == bins.numcols())
    		{
    			col = 0;
    			//cout << row << " " << col << endl;
    			if (row+1 < bins.numrows())
    				row++;
    		}
    	}
    }
    
    // Function: radixSort
    // Sorts numbers in list into ascending order
    //
    // Inputs: list and its length
    // Outputs: the list with numbers sorted in ascending order
    
    template<class element>
    void radixSort(apvector<element> &list, int n)
    {
    	int j, k;
    	apmatrix<element> bins(10,MAX_LIST_SIZE);
    	apvector<int> binCounters(10);
    
    	initializeCounters(binCounters);
    
    	// For k loop controls digit used to classify data.
    	for (k = 1; k <= 4; k++)
    	{
    		// For j loop iterates through all numbers, putting them into
    		// bin determined by kth digit.
    		for (j = 0; j < n; j++)
    			addToBin (bins, binCounters, list[j], digit(list[j], k));
    		collectBins (list, bins, binCounters);
    		initializeCounters(binCounters);
    	}
    }
    Last edited by Trauts; 03-05-2003 at 12:11 PM.

  9. #9
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Do you understand EXACTLY how radix sort works? If so, then you shouldn't have a problem debugging your code. Just go step by step and testing it to make sure that it is doing what it is supposed to.

    You need binsCounter[place]++ to increment the values, otherwise when you place the numbers into the bins, they will constantly be overwritten at the zero spot. Think about, if its not in there then, then why do you even both constantly initializing them, they will always be zero!

    By the way, I've tested it and using
    ++i is SLOWER than using i++ by a tiny amount. So if you need a speedier program, use i++
    Thats funny, I've tested it to and I got the opposite results. Oh well, doesn't matter, the difference is so small that its negligible.

  10. #10
    Registered User
    Join Date
    Sep 2002
    Posts
    417
    Originally posted by Trauts
    I tried using that and it gives another illegal index.
    weird... must depend on the compiler with ++i and i++

    Besides, when I did what you said (I realized I needed that after I relooked at my function, but your code would have helped), only it doesn't work: it gives this:

    illegal vector index: -5 max index = 9;

    And in the debugger, if I try to display what binCounters[place] is, it gives this:

    binCounters[place] CXX0034: Error: types incompatible with operator

    Where the [place] SHOULD be returning an integer. It doesn't give me that problem unless I use the debugger, but thats obviously why the code isn't working.

  11. #11
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Sounds like there is something wrong with the integer place... add this right above your code in the addToBin:
    Code:
    cout<<place<<endl;
    cout<<binCounters[place]<<endl;

  12. #12
    Registered User
    Join Date
    Sep 2002
    Posts
    417
    I think it might actually be the collectbins function. I rewrote it on a piece of scrap paper, I'll try it tomarrow. Thanks.

    If you look at it, it isn't really good to do it in one loop, you need nested ones.

  13. #13
    Registered User
    Join Date
    Sep 2002
    Posts
    417
    Originally posted by PJYelton
    Sounds like there is something wrong with the integer place... add this right above your code in the addToBin:
    Code:
    cout<<place<<endl;
    cout<<binCounters[place]<<endl;
    I don't think it could be place because I can cout just fine the value of it, and the debugger can see it.

  14. #14
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    If you put in the couts like I said, what does place and binCounters[place] equal just before the invalid index error?

    Your collectbins needs to be something like (in pseudocode):
    Code:
    for (int x=0; x<10; x++)
    {
        for (int y=0; y<binCounters[x]; y++)
        {
            add bins[x][y] to the list
        }
    }

  15. #15
    Registered User rmullen3's Avatar
    Join Date
    Nov 2001
    Posts
    330

    ~

    "By the way, I've tested it and using
    ++i is SLOWER than using i++ by a tiny amount. So if you need a speedier program, use i++"

    While the computer is a strange animal, I don't see why postfix would be any faster at all...
    "He who makes a beast of himself, gets rid of the pain of being a man." Dr. Johnson

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. My own itoa()
    By maxorator in forum C++ Programming
    Replies: 18
    Last Post: 10-15-2006, 11:49 AM
  2. Using quicksort and radix sort for an anagram program
    By RazielX in forum C Programming
    Replies: 2
    Last Post: 05-03-2004, 09:33 AM
  3. radix sort and radix exchange sort.
    By whatman in forum C Programming
    Replies: 1
    Last Post: 07-31-2003, 12:24 PM
  4. Radix Sort, Strings, and Linked Lists
    By dark paladin in forum C++ Programming
    Replies: 2
    Last Post: 04-24-2003, 03:24 PM
  5. Radix Sort question
    By ripper079 in forum C++ Programming
    Replies: 5
    Last Post: 01-06-2003, 06:58 AM