Description
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
- a) Insertion sort (slide 5)
- b) Shell sort with sequence 5,3,1 (slides 14, 15, 16)
: c) Merge sort (as slide 30)
: d) Radix sort (as slide 59).
Note: continue each until the final list is sorted!
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.
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).
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!
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
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?
