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);
	}
}

First off, are you sure apmatrix and apvector are implemented correctly?
Looking over the posted code now....

gg

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.

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

The digit function is close, just change it to:

Code:

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

and it should work.

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]

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++

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);
	}
}

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.

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.

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 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.

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.

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
    }
}

"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...