Chapter 7
1) For the list shown below, illustrate each of following sorts as shown in the slide(s) listed:
64, 32, 79, 83, 67, 46, 96, 55, 68, 12
10 points: a) Insertion sort (slide 5)
15 points: b) Shell sort with sequence 5,3,1 (slides 14, 15, 16)
10 points: c) Merge sort (as slide 30) 10 points: d) Radix sort (as slide 59).
Note: continue each until the final list is sorted!
15 points
2) For the list shown below, demonstrate the following sort:
64, 12, 68, 23, 97, 38, 81, 76, 55, 32, 48, 29, 46
Quick sort (as slide 45). Use median-of-three and continue until the list is sorted. If a partition size is <= 3, just put the partition in sorted order.
10 points
3) For the list shown below, demonstrate the following sort: 8, 7, 4, 2, 5, 5, 2, 4, 5, 7, 8 Bucket sort (as slide 57).
10 points
4) For the list shown below, demonstrate the following sort:
10, 1, 5, 2, 6, 8, 4, 10, 6, 6, 2, 4, 1, 8, 7, 3 External sort (as slide 61). Use a run size of 4.
Note: continue until the final list is sorted!
10 points
5) For the list below, what runs would be created if M=3 using replacement selection?
10, 1, 5, 2, 6, 8, 4, 10, 6, 6, 2, 4, 1, 8, 7
10 points
6) Suppose 4 items are to be compared. How many leaves would the decision tree have for this number of items? How many comparisons at worst would it take to sort them?
Submit to eLearning: hw7.doc (.doc can be .txt, .jpg, etc.)
