# 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:&#x20;

* 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&#x20;
* Insertion sort: determine where to insert the current item

The core idea behind Quicksort involves **partitioning.**&#x20;

Specifically, to partition an array a\[], first pick an element x = a\[i] as the pivot.&#x20;

<figure><img src="https://lh6.googleusercontent.com/uFsnl6huFGAYsN7Tsk4-0F3mBDUDZ9Cobaeq3cWeDs4kWvE3d2-4Zyp3QLzNxuUipSOMJvSUmTlQWqpnasgMNkBqv6s4Cu-ndfIv-tkLJ8QhjibVJYwTEBmOQM6utO8z8M8S58wvuxMgiedvLqcllFY" alt=""><figcaption><p>In this array, x = 10 and is the pivot element. This array has not be partitioned on x = 10 yet. </p></figcaption></figure>

Partitioning on that pivot element (x) involves rearrange a\[] such that:&#x20;

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)&#x20;
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.

<figure><img src="https://lh5.googleusercontent.com/SFSKi0Tx5zqOkkBagtljRD__IHEeIoGzOa3jipkmRt_lxYZKFh5mqEMOsLjy1LvSzgA4wXW5qHvMfx7im3vhw6fD-er0XTA9cc-fTmASeB1oeYksBPVaGFRkIt0JLjorRdsG8TDWguvHDad9NM4MTRg" alt=""><figcaption><p>D is an invalid partition because 4 is less than 10, but is to the right of the pivot after the partition. </p></figcaption></figure>

\
