31.1 Partitioning

Previously, we’ve covered selection sort, heap sort, merge sort, and insertion sort.

These sorts each have a basic idea powering them:

• Selection sort: find the smallest item, put it at the front
• Heap sort: use MaxPQ to find the maximum element, put it at the front
• Merge sort: merge two sorted halves into one sorted whole
• Insertion sort: determine where to insert the current item

The core idea behind Quicksort involves partitioning.

Specifically, to partition an array a[], first pick an element x = a[i] as the pivot.

Partitioning on that pivot element (x) involves rearrange a[] such that:

1. x moves to some position j (can be the original position of i)
2. All array elements to the left of x are less than or equal to x (<= x)
3. All array elements to the right of x are greater than or equal to x (>= x)