> For the complete documentation index, see [llms.txt](https://cs61b-2.gitbook.io/cs61b-textbook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cs61b-2.gitbook.io/cs61b-textbook/30.-quicksort/30.1-partitioning.md). # 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.