Question Details

Your task in this activity is to compare running time of radix sort on an array of integer with r=10, r=100, and r=1000.

For decimal numbers, r=10, the size of the alphabet is 10 since there are 10 items in the set of {0, 1, ...9}. Because of this, size of the counter array is 10, which is given in the example code as int cnt[RB]= {0}.

We want to fasten radix sort by expanding size of the alphabet from 10 to 100 and 1000. for example, with r=100, the alphabet will be {00, 01, 02,... 97, 98, 99}. 

Follow these steps:

Randomly create 256K integers between 100000 and 999999 and keep in three arrays. They will be three copies of same array.

Sort first array with radix sort, r=10. You process only one digit per iteration. For example, the iteration items will be 5, 3, 1, 0, 9, and 7 for 790135. The example code given this week is sorting with r=10. Report the running time.

Sort second array with r=100, in which you need to process two digits per iteration. These are 35, 01, and 79 for 790135. Report the running time.

Sort third array with r=1000 in which you need to process three digits per iteration, i.e., 135 and 790 for 790135. Report the running time

Report the running times in millisecond the following format:

r=10,     207 ms

r=100,     67 ms

r=1000,   23 ms

Your program should have only one radix-sort function, which is called for all three sorting operation. This means you do not implement three different radix-sort function.