/*
* By: Alvin Raj
* Date: 12 August 2002
* Algorithm adapted from: C++ Data Structures, Nell Dale
*
*
*/
public class RadixSortAlgorithm extends SortAlgorithm {

// for each of the 10 digits

// Assumes all positive integers
// numbDigits is the number of digits in the largest number
void sort(int a[] , int numDigits) throws Exception {
int arrayPos;
for (int i = 1; i <= numDigits; i++) {
if (stopRequested) {
return;
}
arrayPos = 0;
// Put values into queues according to radix
// least significant digit first, then second,...
// first pass sorts on least significant digit
for (int j = 0; j < a.length; j++) {
pause(-1,j); // JH
}
// Collect the queues and put them back into the array
// queues contain partially sorted lists after first
// pass -- moving to next significant digit will
// maintain this ordering.
for (int j = 0; j < Q.length; j++) {
while(!Q[j].isEmpty()) {
a[arrayPos] = Q[j].dequeue();
arrayPos++;
}
pause(-1,arrayPos);
}
}
}

void sort(int a[]) throws Exception {
// Find the largest entry in a[]
int max = 0;
int maxIndex = 0; // JH
for (int i = 0; i < a.length; i++) {
if (max < a[i]) {
max = a[i];
maxIndex = i; // JH
pause(maxIndex, i); // JH
}
}

int numDigits = 1;
int temp = 10;
// compute the max number of digits
// JH: this could be more easily be computed by using
// numDigits = (int) log(base10, max)
while (true) {
if (max >= temp) {
numDigits++;
temp*=10;
}
else
break;
}

//call the sort
sort(a,numDigits);
}

//returns the radix of the given number
//EG:
//2nd radix of 79981 is 8
//1st radix of 79981 is 1