Problem 1 [8 points]

Show the execution of quick sort on the following array. You should show the array after each call to partition. Explicitly state your pivot selection strategy.

34 19 3 22 5 2 46 30

Problem 2 [8 points]

Show the execution of shell sort on the following array. Use gaps of three, two, and one. You should show the array after each pass.

34 19 3 22 5 2 46 30 17 8 41 23

Problem 3 [4 points]

Banks often record transactions on an account in the order of the times of the transactions, but many people like to receive their bank statements with checks listed in order by check number. Because people will write checks in order by number and merchants will tend to cash them rather promptly, the problem is one of sorting almost-sorted input (converting time-of-transaction ordering to check-number ordering). Considering insertion sort, mergesort, and quicksort, explain which one would be best for the problem.