Input:

Output:

Algorithmic Strategy:

• Divide: Select an element in the array A[p...r] (initially p=1, r=n), say for instance x=A[r], which we will call the pivot, and rearrange the elements in the array A such that for some index q, p ≤ q ≤ r, x is located in A[q], all the elements in A that are less than or equal to x are located to the left of x (i.e., in A[p...q-1])., and all the elements in A greater to x are located to the right of x (i.e., in A[q+1...r]).

• Conquer: Recursively call quicksort to sort the subarrays A[p...q-1] and A[q+1...r].

• Combine: No need to do anything additional, since after A[p...q-1] and A[q+1...r] are sorted then A[p...q-1 q q+1...r] will be sorted.

Algorithm:

quicksort(A,p,r) {

    If p < r then {
        q := partition(A,p,r) 
        quicksort(A,p,q-1)
        quicksort(A,q+1,r)
    }
}

partition(A,p,r) {
    x := A[r]
    i := p-1
    For j := p to r-1 do {
        If A[j] ≤ x then {
            i := i+1
            exchange A[i] with A[j]
        }
    }
    exchange A[i+1] with A[r]
    return i+1
}

       p         i           j             r
       -------------------------------------
      | | | | | | | | | | | | | | | | | | |x|
       -------------------------------------   
      |...........|.........|.............|
           ≤ x        > x    not processed
                                  yet          

• (10 Points). Follow the full quicksort algorithm (including the partition function) by hand showing step by step the values of the array A and all the variables used in quicksort and partition during the sorting of the array below. Be as neat as possible.

         ---------------
      A |7|6|5|4|8|2|3|6| 
         ---------------
  

• (10 Points). Prove that quicksort is correct, that is, prove that it always returns the original elements of the input array A correctly sorted.

• (10 Points). Show in detail that the runtime of the partition algorithm is Θ(n).

• (10 Points). Consider the worst-case partitioning for quicksort. In this case, the array is partitioned into two subarrays, one with n-1 elements and the other one with 0 elements. Assume that this worst-case behavior happens on each one of the recursive calls. Since you showed above that the partition algorithm is Θ(n), then quicksort's runtime for this worst-case is T(n) = T(n-1) + T(0) + Θ(n) = T(n-1) + Θ(1) + Θ(n) = T(n-1) + Θ(n) Use either the recursion-tree method (= "unrolling" the recurrence) or the substitution method (= "guess + induction") to show that T(n) = O(n²).

• (10 Points). Consider the best-case partitioning for quicksort. In this case, the array is partitioned into two subarrays, of equal size (or nearly equal size if n is odd). Provide a recurrence for T(n) in this best-case and determine the tightest upper bound you can for T(n) (here you can reuse results proven in class or in the textbook (without proving them again) to determine this tightest upper bound, if appropriate).

• (15 Points). Use the recursion-tree method (= "unrolling" the recurrence) to prove in detail that T(n) = O(n^log₃4).

• (15 Points). Use the substitution method (= "guess + induction") to prove in detail that T(n) = O(n^log₃4).