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
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?
4 items have 4! possible arrangements. this leads to a tree with 4! = 24 leaves, thus log(4!) depth, and therefore log(4!) comparisons. therefore the number of comparisons required is 5.
Submit to eLearning:
hw7.doc (.doc can be .txt, .jpg, etc.)
