Understanding the partitioning routine in Quick Sort

In our previous article, we introduced the quick sort algorithm, a powerful and efficient sorting technique. At the heart of quick sort lies a fundamental operation called “partitioning.” This step involves dividing and organizing an unsorted array into two sections based on a chosen element called the “pivot.” Partitioning rearranges the array so that elements are properly positioned relative to the pivot, creating smaller portions of array that can be sorted independently. In this article, we’ll break down the concept of partitioning in quick sort in a simple, beginner-friendly way.

What is Partitioning?

Partitioning is a crucial step in the quick sort algorithm. It’s the process of rearranging elements in an array around a chosen “pivot” element. The pivot is simply a selected element from the array that we use as a reference point for comparison. The goal is to ensure that:

  • All elements less than the pivot come before it.
  • All elements greater than the pivot come after it.
  • The pivot itself is in its final sorted position.

Think of it this way: Imagine you have a line of students, and you want to arrange them so that everyone shorter than a specific student (the “pivot”) stands to their left, and everyone taller stands to their right. After you’re done, that specific student (the pivot) will be in the exact spot they’d be in if the entire line was sorted by height.

Why is Partitioning Important?

Partitioning is the heart of the quick sort algorithm. It’s allows quick sort to efficiently sort an array by breaking it down into smaller, more manageable sub-problems. Here’s why it’s so important:

  1. Places the Pivot Correctly: After partitioning, the pivot element is in its final sorted position. This means we don’t need to consider it again in future steps.

  2. Creates Sub-arrays: Partitioning divides the original array into two smaller sub-arrays:

    • One with elements less than the pivot.
    • One with elements greater than the pivot.
    • It’s like putting up a fence (the pivot) in the middle of a field.
    • Everything on one side of the fence (the pivot) stays on that side, and everything on the other side stays on its side.

  3. Enables Recursion: Quick sort can then be applied recursively to these smaller sub-arrays separately. This “divide and conquer” approach is what makes quick sort so efficient. We only need to sort the elements within each sub-array, making the problem smaller and easier to solve.

If you need a refresher, here’s a helpful link to the introduction of quick sort article: Introduction to Quick Sort Algorithm.

How Partitioning Works: Step-by-Step

Let’s break down the partitioning process using a simple example. Imagine we have the following list of numbers (an array):

[4, 6, 7, 3, 5]

We need to pick a number from this list to be our pivot. For this example, let’s choose the last number, which is 5.

Our goal is to rearrange the list so that all numbers smaller than 5 are on its left, and all numbers larger than 5 are on its right. The number 5 itself should end up in its final sorted position.

Think of it like this: We have a basket of mixed fruits, and we pick one fruit (the pivot, our 5). We want to put all fruits smaller than it to one side and all fruits larger than it to the other side.

To do this, we’ll use two imaginary markers (pointers):

  1. j (the Explorer): This pointer will travel through the list from left to right, looking at each number one by one (except the pivot itself, for now).
  2. i (the Boundary Marker): This pointer marks the boundary between the “smaller than pivot” section and the section we haven’t processed yet. It starts just before the list begins (at index -1). i only moves forward when we find an element smaller than the pivot.

Let’s start!

  • Initial State:

    • Array: [4, 6, 7, 3, 5]
    • Pivot: 5 (at the end, index 4)
    • i is at -1
    • j starts at index 0

  • Step 1: j looks at 4 (index 0)

    • Question: Is 4 less than our pivot 5? Yes.
    • Action:
      1. Move the boundary marker i one step forward (from -1 to 0).
      2. Swap the element at index i (4) with the element at index j (4). (It swaps with itself, so no visible change).
    • Array: [4, 6, 7, 3, 5] (i is now at index 0, j moves to index 1)

  • Step 2: j looks at 6 (index 1)

    • Question: Is 6 less than 5? No.
    • Action: Do nothing. Just move j forward.
    • Array: [4, 6, 7, 3, 5] (i stays at index 0, j moves to index 2)

  • Step 3: j looks at 7 (index 2)

    • Question: Is 7 less than 5? No.
    • Action: Do nothing. Just move j forward.
    • Array: [4, 6, 7, 3, 5] (i stays at index 0, j moves to index 3)

  • Step 4: j looks at 3 (index 3)

    • Question: Is 3 less than 5? Yes.
    • Action:
      1. Move i forward (from 0 to 1).
      2. Swap the element at index i (6) with the element at index j (3).
    • Array: [4, 3, 7, 6, 5] (i is now at index 1, j moves to index 4)

  • Step 5: j reaches the pivot

    • Our explorer j has looked at all elements before the pivot. Now, it’s time to put the pivot in its correct place.
    • The boundary marker i is currently at index 1. This means all elements up to index 1 (4, 3) are smaller than the pivot 5.
    • The correct spot for the pivot is right after this “smaller” section, which is at index i + 1 (index 2).
    • Action: Swap the element at i + 1 (which is 7) with the pivot (5).
    • Array: [4, 3, 5, 6, 7] (i is still index 1)

  • Final Result:

    • Our list is now: [4, 3, 5, 6, 7]
    • Notice:
      • All numbers less than 5 (4, 3) are to its left.
      • All numbers greater than 5 (6, 7) are to its right.
      • The pivot 5 is now sitting in the exact position it would be if the entire list were sorted!

This process is called partitioning. We’ve successfully divided the list into two parts around the pivot. Quick sort will then repeat this process on the left part ([4, 3]) and the right part ([6, 7]) separately until the entire list is sorted.

Different Partitioning Schemes & Strategies

The step-by-step example we walked through demonstrates one common way to partition an array, known as the Lomuto partition scheme. This scheme typically uses the last element as the pivot and one main pointer (j) to scan the array, swapping smaller elements towards the beginning marked by another pointer (i).

However, Lomuto’s isn’t the only way! There are other methods, each with slightly different approaches and advantages:

  • Hoare Partition Scheme: This scheme usually uses two pointers, one starting near the beginning of the array and one near the end.

    • The left pointer moves right, looking for an element greater than or equal to the pivot.
    • The right pointer moves left, looking for an element less than or equal to the pivot.
    • Once both pointers find such elements (or cross each other), the elements they point to are swapped.
    • This process repeats until the pointers meet or cross.
    • Hoare’s scheme is often slightly faster than Lomuto’s on average because it does fewer swaps, but it can be a bit trickier to implement correctly. A key difference is that the pivot’s final position isn’t necessarily determined until the recursive calls finish.

  • Three-Way Partitioning (Dutch National Flag problem): This approach is particularly useful when the array might contain many duplicate elements equal to the pivot. Instead of just two partitions (less than pivot, greater than pivot), it creates three:

    • Elements less than the pivot.
    • Elements equal to the pivot.
    • Elements greater than the pivot.
    • By grouping all equal elements together in one step, it can significantly speed up sorting arrays with lots of duplicates. Think of sorting pebbles by color into three piles: black, white, and grey.

  • Other Variations: Beyond these main schemes, variations exist. Some might:

    • Choose the pivot differently (e.g., always pick the first element, pick a random element, or pick the median of three elements to try and avoid worst-case scenarios).
    • Handle elements equal to the pivot in specific ways within the two-partition schemes.

While the above approaches differ slightly, the core purpose of any partitioning scheme in quick sort remains the same: efficiently rearrange a section of the array around a chosen pivot, placing the pivot closer to (or exactly in) its final sorted position and dividing the problem into smaller, independent sub-problems. The choice of scheme can impact performance, especially in specific scenarios like arrays with many duplicates.

Key Takeaways

  • Partitioning rearranges an array around a pivot so that smaller elements come before it, and larger elements come after it.
  • The pivot ends up in its final sorted position after partitioning.
  • Partitioning creates two sub-arrays that can be sorted recursively.
  • There are different partitioning schemes (Lomuto, Hoare, etc.), but they all achieve the same basic goal.

What’s Next?

Now that you have a good understanding of partitioning, you might want to: