Course contentsShow
← Computer Science
Lesson 257 of 2,8726. Arrays and Basic CollectionsFree lesson

Partitioning Arrays Around a Pivot

Rearrange array elements so values less than pivot come before values greater than pivot, foundational for quicksort.

Partitioning Arrays Around a Pivot

What you'll learn: How to rearrange an array so all elements smaller than a chosen "pivot" value come before those that are larger—a foundational technique for efficient sorting.


Core Idea

Imagine you're organizing books on a shelf by height, but you pick one book as your reference point (the "pivot"). You move all shorter books to the left of it and all taller books to the right. That's partitioning!

In an array, you choose one element as the pivot (often the last element, first element, or middle one). Then you rearrange the array so that:

  • All values less than the pivot appear before it
  • All values greater than the pivot appear after it
  • The pivot ends up in its "correct" sorted position

You don't fully sort the array—just organize it around that one value.


How It Works

Start with two pointers or indices: one scanning from the left, one working from positions you've checked. As you iterate through the array:

  1. Compare each element to the pivot
  2. If smaller than the pivot, swap it toward the front section
  3. If larger, leave it for the back section
  4. Place the pivot between the two sections

After partitioning [8, 3, 7, 1, 9, 5] around pivot 5, you might get [3, 1, 5, 7, 9, 8]. Notice 3 and 1 are before 5; 7, 9, and 8 are after. The exact order within each section doesn't matter yet.


Why It Matters

This operation is the heart of quicksort, one of the fastest sorting algorithms. By repeatedly partitioning smaller and smaller sections, you eventually sort the entire array efficiently.

Key Takeaway: Partitioning rearranges an array around a pivot value so smaller elements migrate left and larger ones right, creating two unsorted groups separated by the pivot—the foundation of quicksort.