Emphasis on: Two-dimensional array processing
A radix sort (commonly
known as a bucket sort) of integers begins with a one-dimensional array of
integers to be sorted, and a two-dimensional array of integers with 10 rows and
n columns, where n is the number of values in the one-dimensional array to be
sorted. Each row of the two-dimensional
array is known as a bucket.
Alternatively you could
use an array with n rows and 10 columns (buckets), though that is more
difficult to program.
Write a function to bucket
sort an array of integers and a program to test your function.
The sort algorithm is as
follows:
1) Loop through the one-dimensional array and
place each of its values in the bucket whose
subscript corresponds to the value of its
one's digit. For example, 97 is placed
in bucket 7,
3 is placed in bucket 3, 140 is placed in
bucket 0, 47 is placed in bucket 7, and 93 is placed in
bucket 3.
2) Loop through the buckets and copy the values
back to the original array (from bucket 0 to
bucket 9, and from first value entered
into the bucket to last). The new order
of the example
values in the one-dimensional array is
140, 3, 93, 97, 47.
3) Repeat this process for each subsequent digit
position (tens, hundreds, etc.) until all possible
digit positions have been processed.
On the second pass of the
array (looking at the tens position), 140 is placed in bucket 4,
3 in bucket 0, 93 in
bucket 9, 97 in bucket 9, and 47 in bucket 4.
The order of the values in the
one-dimensional array is
now 3, 140, 47, 93, 97.
On the third pass, 3 is
placed in bucket 0, 140 in bucket 1, 47 in bucket 0, 93 in bucket 0, and
97 in bucket 0. The bucket sort is guaranteed to have all the
values properly sorted after
processing the leftmost
digit of the largest number. The bucket
sort knows it is done when all
the values are copied into
bucket 0.
The bucket sort requires
one pass through the array for each possible digit in the numbers to be
sorted. If you don't know the maximum
number of digits in your largest number, you'd have to make another pass. When all the numbers are in the 0 bucket, you
know they are sorted.
Note that the memory
required for the ten buckets is ten times the size of the array being
sorted. This sorting technique provides
better performance in terms of speed than many sorts, but requires much larger
data storage capacity. Bucket sort is an
example of a time-space tradeoff. It
performs faster than many sorts, but uses considerably more memory.
You are to use a random
number generator to fill an array with integers in the range 0 to 32,000,
Inclusive. This array should be passed to your Bucket
Sort function to be sorted into ascending order. Print the values in their original order
first and then again after each pass through the array, ending with the values
in their sorted order.
Program Requirements:
1. The bucket sort must be written as a
function. Parameters passed are the
one-dimensional
array to be sorted and the number of
elements in the array.
2. The bucket array must be implemented as a
two-dimensional array.
3. Test your function with two different random
sequences of integers, one of them a sequence
of 25 integers and the other a sequence of
20 integers.
4. Your sort should not depend on knowing the
maximum number of digits in the values to be
sorted (test for all values in the 0
bucket).
Random Number Generator
The standard library function rand() returns a random
number such that 0 <= rand() < 32767.
To convert this into a number within a specific range 1 .. n , use the algorithm rand()
% n + 1 .
For instance, if we were simulating rolling dice, we would
want a number in the range 1 .. 6, so we could code something like: die = rand() % 6 + 1 .
To obtain a number within the range 0 .. n , use the algorithm rand() % (n + 1) .
The random number generator is initialized (needs to be
called only once) by a call to the standard library function srand() . You can pass srand a specific value (good for
testing purposes until you're sure your program is working correctly), or you
can initialize it with a value from the system clock (for a random starting
seed):
srand (237); or srand (unsigned (time (NULL)));
To use the rand and srand functions, include stdlib.h (or cstdlib), and to use the time function, include time.h (or ctime).
Here’s another example sorting these numbers: 25
150 53 254
300 4 355
404 523 225
80
Buckets after the first pass:
|
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
… |
|
0 |
150 |
300 |
80 |
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
3 |
53 |
523 |
|
|
|
|
|
|
|
|
4 |
254 |
4 |
404 |
|
|
|
|
|
|
|
5 |
25 |
355 |
225 |
|
|
|
|
|
|
|
6 |
|
|
|
|
|
|
|
|
|
|
7 |
|
|
|
|
|
|
|
|
|
|
8 |
|
|
|
|
|
|
|
|
|
|
9 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Emptying out the buckets, we have: 150
300 80 53 523 254
4 404 25
355 225
Buckets after the second pass:
|
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
… |
|
0 |
300 |
4 |
404 |
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
2 |
523 |
25 |
225 |
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
4 |
|
|
|
|
|
|
|
|
|
|
5 |
150 |
53 |
254 |
355 |
|
|
|
|
|
|
6 |
|
|
|
|
|
|
|
|
|
|
7 |
|
|
|
|
|
|
|
|
|
|
8 |
80 |
|
|
|
|
|
|
|
|
|
9 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Emptying out the buckets again, we have: 300
4 404 523 25 225
150 53 254
355 80
Buckets after the third pass:
|
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
… |
|
0 |
4 |
25 |
53 |
80 |
|
|
|
|
|
|
1 |
150 |
|
|
|
|
|
|
|
|
|
2 |
225 |
254 |
|
|
|
|
|
|
|
|
3 |
300 |
355 |
|
|
|
|
|
|
|
|
4 |
404 |
|
|
|
|
|
|
|
|
|
5 |
523 |
|
|
|
|
|
|
|
|
|
6 |
|
|
|
|
|
|
|
|
|
|
7 |
|
|
|
|
|
|
|
|
|
|
8 |
|
|
|
|
|
|
|
|
|
|
9 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Emptying out the buckets again, we have: 4
25 53 80 150 225
254 300 355
404 523
After the next pass, all the values are sorted into the 0
row (bucket) and the other buckets are empty.