AlgoScope

Partition

Push everything smaller than the pivot to its left, then drop the pivot between the groups.

Array algorithms and techniques, algorithm, intermediate
The pivot 7 moves to index 5. Everything to its left is smaller and everything to its right is not.range 0-650114223347586ipivot
The pivot 7 moves to index 5. Everything to its left is smaller and everything to its right is not.range 0-650114223347586ipivot

Quick Sort: Seven values

Step, step 9 of 29

Swap the pivot 7 with 8 so it lands between the two groups.

Cost

Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(1)

Before this

Variants

  • Lomuto PartitionSingle scan with a boundary index.
  • Hoare PartitionTwo pointers converge from both ends.

Leads to

Topics that need this one first.

Taught by the same lesson

Quick Sort covers these too, in the same run.