Chapter 4: QuickSort

D&C(Divide and Conquer)

• • Figure out a simple case as the base case.

  • Figure out how to reduce your problem and get to the base case.

• Quicksort

  • Quicksort is unique because its speed depends on the pivot you choose.

  • First, pick an element from the array. This element is called the pivot.

  • Now find the elements smaller than the pivot and the elements larger

    than the pivot.This is called partitioning.

  • Ex:

    def quicksort(array): 
      if len(array) < 2:
        return array   //Base case: arrays with 0 or 1 element are already “sorted.”
      else:
        pivot = array[0]    // Recursive case
        less = [i for i in array[1:] if i <= pivot]    //Sub-array (Less than pivot)
        greater = [i for i in array[1:] if i > pivot]  //Sub-array (Greater than pivot)
      return quicksort(less) + [pivot] + quicksort(greater) 
    ​
    print quicksort([10, 5, 2, 3])     =>[2,3,5,10]

• Inductive Proofs

  • You just got a sneak peak into inductive proofs! Inductive proofs are one way to prove that your algorithm works. Each inductive proof has two steps: the base case and the inductive case.