CISC 3220

Assignment #5, Due: Wednesday, October 26.

    Quicksort:

  1. Show the first two iterations of Quicksort on the following array:

    10 9 8 7 6 5 4 3 2 1


  2. Suppose you are given an unsorted array where each element is either a 0 or 1.
    1. What is the asymptotic order of the number of comparisons done by Quicksort in the worst case? (describe the worst case input)
    2. Give a more efficient algorithm for sorting an array of n elements which are all 0's or 1's. Analyze the worst case time complexity of your algorithm.
  3. Try to modify the partition that we saw in class to solve the following problem in linear time:

    Given an array of n elements, each element having one of the values: red, white, or blue. Give an efficient algorithm for reordering the array so that all the reds come before whites, and all whites come before blue. The only operations permitted are to examine a key for its color, and a swap of two elements.

    4. Heapsort:

  4. Does the following array represent a max-heap? Justify your answer.

    30 24 20 10 17 9 18 8 12 15
  5. Suppose the array to be sorted by Heapsort intially contained the following sequence:
    C O M P L E X I T Y
    Show how they would be arranged in the heap after the heap construction phase. Exactly how many comparisons are done to the construct the heap with these keys?