Lesson 10: Quick Sort

Quick sort is a divide-and-conquer sorting algorithm. It chooses a value called a pivot, partitions the list around that pivot, and then recursively sorts the smaller partitions.

After partitioning:

• values smaller than the pivot are placed on one side
• values greater than the pivot are placed on the other side
• the pivot ends up in its sorted position

Common Pivot Choices

A quick sort implementation may choose:

1. the first element
2. the last element
3. a random element
4. a median-like value

Partitioning

The partition step is the key part of quick sort. Given a pivot, the algorithm rearranges the array so the pivot is placed where it belongs in the sorted order.

Example:

Original:  {10, 3, 30, 25, 48, 4, 36}
Sorted:    {3, 4, 10, 25, 30, 36, 48}

Quick sort reaches the sorted result by repeatedly partitioning smaller sections of the list.

---