# 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.