7.5

Implement a radix sort as described in the last section of this chapter. It should handle variable amounts of data and variable numbers of digits in the key. You could make the number-base variable as well (so it can be something other than 10), but it will be hard to see whats happening unless you develop a routine to print values in different bases.

Hint:

class ArrayRad

{

private int maxDigits; // # of digits in key

private int base; // number base (try 10)

private int maxItems; // max # of data items

private int nItems; // current # of items

private long maxKey; // largest data item (999

// for 3 base-10 digits)

long dataArray[]; // array for data

FirstLastList[] listArray; // array of lists

.

}

Use this main, You MUST use this main method in order to solve the assignment:

public static void main(String[] args)

{

int maxDigits = 3; // # of digits in key

int base = 10; // number base

int maxItems = 15; // number of items to sort

// make an ArrayRad

ArrayRad arr = new ArrayRad(maxDigits, base, maxItems);

long maxKey = arr.getMaxKey(); // get maximum key value

System.out.println("maxKey=" + maxKey);

for(int j=0; j

{ // random numbers <= maxKey

long n = (int)(java.lang.Math.random()*(maxKey + 1));

arr.insert(n);

}

System.out.println("Unsorted array:");

arr.display();

System.out.println("");

arr.radixSort(); // radix sort the items

System.out.println(" Sorted array:");

arr.display();

} // end main()

The output MUST be this one below, in form and content:

maxKey=999

Unsorted array:

338 831 918 928 691 940 822 211 92 757 202 663 563 725 697

Sorted on position 1

940 831 691 211 822 92 202 663 563 725 757 697 338 918 928

Sorted on position 2

202 211 918 822 725 928 831 338 940 757 663 563 691 92 697

Sorted on position 3

92 202 211 338 563 663 691 697 725 757 822 831 918 928 940

Sorted array:

92 202 211 338 563 663 691 697 725 757 822 831 918 928 940