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

In this array, x = 10 and is the pivot element. This array has not be partitioned on x = 10 yet.

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)

In the following arrays, A, B, and C represent arrays that are valid partitions (with the pivot being x = 10), while D represents an invalid partition.

D is an invalid partition because 4 is less than 10, but is to the right of the pivot after the partition.