Homework #9

Deadline: The source code for this program (bucket.cpp) and its executable (bucket.exe) must be available in your home directory (i.e., cpsuser3.cps.udayton.edu/cps150/sectionn1/cps150-N1.[your number goes here]) by 5:50p on Wednesday, November 10, 2004. Also, turn in a printout of your code in class, before class starts.

Note: You must use the filenames exactly as shown above (i.e., all lower case).

Problem: A bucket sort begins with a one-dimensional array of positive integers to be sorted and a two-dimensional array of integers with rows subscripted from 0 to 9 and columns subscripted from 0 to n-1, where n is the number of values in the array to be sorted. Each row of the 2-dimensional array is referred to as a "bucket." Write a function bucket_sort that takes an integer array and the array size as arguments and performs as follows:
  1. Place each value of the one-dimensional array into a row of the bucket array based on the value's ones digit. For example, 97 is placed in row 7, 3 is placed in row 3, and 100 is placed in row 0. This is called a "distribution pass."
  2. Loop through the bucket array row by row, and copy the values back to the original array. This is called a "gathering pass." The new order of the preceding values in the one-dimensional array is 100, 3, and 97.
  3. Repeat this process for each subsequent digit position (tens, hundreds, thousands, and so on).
On the second pass, 100 is placed in row 0, 3 is placed in row 0 (because 3 has no tens digit), and 97 is placed in row 9. After the gathering pass, the order of the values in the one-dimensional array is 100, 3, and 97. On the third pass, 100 is placed in row 1, 3 is placed in row 0, and 97 is placed in row 0 (after the 3). After the last gathering pass, the original array is now in sorted order.

Note: The 2-dimensional array of buckets is 10 times the size of the integer array being sorted. This sorting technique provides better performance than a bubble sort, but requires much more memory. The bubble sort requires space for only one additional element of data. This is an example of the space-time tradeoff: The bucket sort uses more memory than the bubble sort, but performs better. This version of bucket sort requires copying all the data back to the original array on each pass. Another possibility is to create a second 2-dimensional bucket array and repeatedly swap the data between the two bucket arrays.

Specifications: Hints:
Return Home