Quicksort

    public static void quicksort(int[] items) {
        quicksort(items, 0, items.length - 1);
    }

    private static void quicksort(int[] items, int left, int right) {
        int pivotindex = (left + right) / 2;

        // curr will be the final position of the pivot item.
        int curr = partition(items, left, right, pivotindex);

        if ((curr - left) > 1) {
            quicksort(items, left, curr - 1); // Sort left partition
        }
        if ((right - curr) > 1) {
            quicksort(items, curr + 1, right); // Sort right partition
        }
    }

    private static int partition(int[] items, int left, 
                                 int right, int pivotindex) {

        int pivot = items[pivotindex];
        swap(items, pivotindex, right); // Stick pivot at end
        pivotindex = right; // remember where it is.

        right--;

        while (left <= right) { // Move bounds inward until they meet
            while (items[left] < pivot) {
                left++;
            }
            while ((right >= left) && (items[right] >= pivot)) {
                right--;
            }
            if (right > left) {
                swap(items, left, right); // Swap out-of-place values
            }
        }
        swap(items, left, pivotindex); // Put pivot in place

        return left; // Return first position in right partition
    }

• Once again, you will play the role of the computer and the algorithm. The computer should shuffle the cards and deal out 8 cards, face down. The algorithm should then trace the steps of the partition (not quicksort!) code above. Once the partition operation has completed, turn the cards face up to check your work.

• Now the computer should re-shuffle the deck and deal out six cards, face down. The algorithm should then trace the operation of the full quicksort implementation shown above. The algorithm should draw the tree of activation records as the sort proceeds.

  
  
  
  
  
  
  
  

• Write recurrences expressing both the best-case and worst-case number of comparisons performed by quicksort, assuming that the partition operation requires \(n-1\) comparisons.

  
  
  
  
  

• Write recurrences expressing both the best-case and worst-case number of array assignments performed by quicksort. (Each swap operation requires two assignments.)

  
  
  
  
  

• Trace the execution of quicksort on the following array. In this case, the key is the number, and the superscript indicates the record.

  \([1^a, 1^b, 1^c, 1^d]\)

  
  
  
  
  
  
  
  
  
  
  

• How many comparisons did quicksort perform for the previous input. (Don’t try to count. You should be able to determine it analytically.)

  
  
  
  
  
  
  

• Is quicksort stable? Justify your answer.

  
  
  
  
  
  
  

• Recall that merge sort performs exactly \(n\log_2 n - n + 1\) comparisons in the worst case. Which is strictly fewer than the number of comparisons performed by quicksort in the average case: \(A(n) \approx 1.39 (n +1) \log_2 n\). How can quicksort be faster?