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.

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.

Last updated