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