## Description

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.)