CSC 220 Fall 2010 Lab 8

CSC220 Lab 8
Due: 10:59AM, Tuesday, November 23

Radix sort is a special sorting algorithm that sorts an array of nonnegative integers as follows.

Suppose that the largest number in the input array has k digits.
For i=1 to k, sort the input array just with respect to the i-th digit from last, in such a way that if there are two numbers x and y having the same digit at the i-th digit position, then the relative order of x and y will be unchanged.

For examnple, let 154, 174, 253, 363, 710, 690 be the input array. In the first round, we sort the numbers with respect to the last digit. This results in: 710, 690, 253, 363, 154, 174. In the second round, we sort the numbers with respect to the middle digit. This results in: 710, 253, 154, 363, 174, 690. In the final round, we sort the numbers with respect to the first difgit. This results in: 154, 174, 253, 363, 690, 710. This completes sorting.

Note the above idea can be applied to octals, binaries, hexes, or even strings.

The goal of this lab is to write a class RadixSort with two static methods,

public static void bitSort(int[] array) and
public static void digitSort(int[] array).

so that both the memory usage and the speed are as small as possible.

About bit-wise sorting.
Note that an int has 32 bits with the top bit allocated for the sign (+ or -) and thus the numbers have only 31 bits. Since there are only two possible values for each bit (0 or 1) and 0 is smaller than 1, for each particular digit position, you have only to:

collect all the numbers with the bit value 0 at that position in the order they appear,
collect all the numbers with the bit value 1 at that position in the order they appear, and then
merge the two collections into one.

Note that the first two tasks can be concurrently executed by scanning the current array from the beginning to the end by keeping the bit-0 numbers in one place and the bit-1 numbers in another place. This would require two separate arrays other than the current array, but optionally you could reuse the current array and then just one additional array would be needed.

About digit-wise sorting.
If we are to replicate the above algorithm for digit-wise sorting, we will need 10 arrays (or 9 arrays if we try to be a bit clever). The idea will be to scan the current array and collect, for each value n = 0, ..., 9, collect all the numbers, in the order they appear, whose digit at the position of interest is equal to n. Since we don't know before hand how many numbers are there with a given digit at a given position, the array size would have to be as large as the input array size. That would be a bit wasteful. So your task is to design something less wasteful than that but still time efficient.