P2: Bucket Sort In previous years, midterm tests were written on paper. After marking all the tests, we would sort all the tests (by student last names) so that entering grades and handing back tests was more efficient. Here is how we would sort the tests. The first step is to create several piles of tests (which we'll call buckets). Each bucket (which is just a pile of tests) will correspond to all the students with last names in a given range. For example, we could make 26 buckets with each bucket holding all students with last names starting with one of the 26 different letters in the alphabet (that is, one bucket for all students with last name starting with "A", one for all students with last name starting with "B", etc.). We then sort each bucket (pile of exams) individually using something like insertion sort. Once each bucket is sorted, if the buckets are arranged in alphabetical order, we can then just pile each bucket on top of each other to have a completely sorted pile of exams. So, we take the "Y" bucket and put it on top of the "Z" bucket, then add the "X" bucket on top of that... until we finally add the "A" bucket to the very top. The end result is one pile of all tests in sorted order. If the names of the students in the class are evenly spread out across the alphabet this makes the sorting process fairly efficient. If everyone in the class has a last name starting with "J", for example, then this method is really bad... (unless we define our buckets differently). This is a form of a bucket sort. In general, a bucket sort does the following: • Create many buckets to store the data needed to be sorted o Each bucket wix hold values in a certain unique range that does not overlap with any other bucket o All values in the data to be sorted must be able to go into some bucket • Take each item in the collection to be sorted and put it in the appropriate bucket • Sort each individual bucket using some other sorting method (like insertion sort) • Combine all the sorted buckets (in the right order) to create one sorted colection of all the data Typically, a bucket sort is used to sort floating point numbers in a given range. Suppose we have a list of numbers where each number is in the range [0,1). That is, each number x satisfies 0sx<1. If the numbers in the list are spread out across this range fairly evenly, we can sort them very efficiently using the bucket sort.