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