2. Consider the following type of Bucket Sort. You have an array of n words, each...

 

Transcribed Image Text:

2. Consider the following type of Bucket Sort. You have an array of n words, each composed of the usual 26 English letters A,B,..., Z Suppose you placed the words in 8 buckets based on the first letter, with buckets for ABC, DEF, GHI, JKL, MN, OPQR, ST, and UVWZYZ. The plan is to sort the 8 buckets and then stack the sorted buckets back into the original array. Don't worry about storage for the buckets. 2.1. (2). The best possible case is for each of the 8 buckets to contain exactly n/8 words. Suppose we sort each of these 8 buckets with selection sort. (not a good sorting method, but it does have an exact work function). Give an exact expression for the total work w(n) required in this best case to sort all 8 buckets. 2.2. (2). The worst case would be if one bucket had all n words and the other 7 buckets had zero works. Give an exact expression for the total work w(n) in this situation. 2.3. (2) To get an idea of the average work, a "probably below average" situation would be if 4 buckets each had n/4 words and the other 4 had zero words. Give an exact expression for the total work w(n) in this situation. Make an effort to write the answer in as simple a form as possible. 2.4. (2) How much work (number if IF statements) is needed to sort the 12 words into the 8 buckets? Hint: is there an optimal way to do this? 2.5. (2) Combining the work discussed in 2.4 and the best case discussed in 2.1, what is the total work needed in the best case? 2.6. (2) Now consider the above problems, except with k buckets rather than 8. Assume that kn. Give a formula in terms of n and k for the best case total work. (formula should reduce to that of 2.5 ifk = 8). 2.7. (2) Consider problem 2.6 except this time use quicksort rather than selection sort for sorting the buckets. For simplicity, assume that quicksort of a size n array always takes exactly Was(n) = anlgn work for some constant a. Give an exact formula for the work needed in terms of n. k. and a. 2. Consider the following type of Bucket Sort. You have an array of n words, each composed of the usual 26 English letters A,B,..., Z Suppose you placed the words in 8 buckets based on the first letter, with buckets for ABC, DEF, GHI, JKL, MN, OPQR, ST, and UVWZYZ. The plan is to sort the 8 buckets and then stack the sorted buckets back into the original array. Don't worry about storage for the buckets. 2.1. (2). The best possible case is for each of the 8 buckets to contain exactly n/8 words. Suppose we sort each of these 8 buckets with selection sort. (not a good sorting method, but it does have an exact work function). Give an exact expression for the total work w(n) required in this best case to sort all 8 buckets. 2.2. (2). The worst case would be if one bucket had all n words and the other 7 buckets had zero works. Give an exact expression for the total work w(n) in this situation. 2.3. (2) To get an idea of the average work, a "probably below average" situation would be if 4 buckets each had n/4 words and the other 4 had zero words. Give an exact expression for the total work w(n) in this situation. Make an effort to write the answer in as simple a form as possible. 2.4. (2) How much work (number if IF statements) is needed to sort the 12 words into the 8 buckets? Hint: is there an optimal way to do this? 2.5. (2) Combining the work discussed in 2.4 and the best case discussed in 2.1, what is the total work needed in the best case? 2.6. (2) Now consider the above problems, except with k buckets rather than 8. Assume that kn. Give a formula in terms of n and k for the best case total work. (formula should reduce to that of 2.5 ifk = 8). 2.7. (2) Consider problem 2.6 except this time use quicksort rather than selection sort for sorting the buckets. For simplicity, assume that quicksort of a size n array always takes exactly Was(n) = anlgn work for some constant a. Give an exact formula for the work needed in terms of n. k. and a.