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

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

<br>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://cs61b-2.gitbook.io/cs61b-textbook-2025/30.-quicksort/30.1-partitioning.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.