How Quick Sort Works: Step-by-Step Explanation

In our previous lessons, we learned about the quick sort algorithm and how the partitioning step works. Now, it’s time to see the complete picture! In this article, we’ll explore how quick sort repeatedly divides an array into smaller parts and sorts them. Think of it like solving a big puzzle by breaking it into smaller, manageable pieces. We’ll walk through each step of the process using simple examples, so you can see exactly how this powerful sorting method transforms an unsorted array into a perfectly ordered one.

Quick Recap

Before we dive into the complete algorithm, let’s refresh our memory on what we’ve learned so far:

  • Quick Sort: This is a sorting method that follows the “divide and conquer” approach. It works by:

    1. Picking one element (called the ‘pivot’)
    2. Putting smaller elements before it and larger elements after it
    3. Repeating this process on the smaller groups until everything is sorted

  • Partitioning: This is the heart of quick sort! During partitioning:

    • Elements smaller than the pivot move to its left
    • Elements larger than the pivot move to its right
    • After partitioning, the pivot is exactly where it should be in the final sorted array

If you’d like to review these concepts in more detail, check out our previous articles:

The Quick Sort Algorithm: Step-by-Step

Let’s illustrate quick sort with an example. We’ll use the array [5, 2, 8, 1, 9, 4, 7, 3, 6] and walk through each step. For simplicity, we’ll use the last element as the pivot in each step.

  1. Initial Array:

    [5, 2, 8, 1, 9, 4, 7, 3, 6]

  2. First Partition:

    • Pivot: 6 (the last element)
    • Partitioning: Rearrange the array so that elements less than 6 come before it, and elements greater than 6 come after it. (See the partitioning article for a detailed breakdown of this process).
    • Result: [5, 2, 1, 4, 3, 6, 7, 9, 8] (The pivot, 6, is now in its final sorted position). All the elements less than 6 are towards the left side of 6 and all the elements more are towards the right side of it.

  3. Recursive Calls:

    Now, we apply quick sort recursively to the two sub-arrays:

    • Left sub-array: [5, 2, 1, 4, 3] (elements less than the pivot)
    • Right sub-array: [7, 9, 8] (elements greater than the pivot)

    Let’s break down each recursive call:

    A. Sorting the Left Sub-array [5, 2, 1, 4, 3]:

    1. Pivot: 3

    2. Partitioning: Rearrange to get, for example, [2, 1, 3, 4, 5] (3 is in its final position)

    3. Recursive Calls:

      • Left: [2, 1]
      • Right: [4, 5]

      Let’s continue with the left sub-array [2, 1]:

      1. Pivot: 1
      2. Partitioning: Rearrange to get [1, 2] (1 is in its final position).
      3. Recursive Calls:
        • Left: [] (empty - base case: nothing to do)
        • Right: [2] (single element - base case: already sorted)

      Now, let’s go back and sort the right sub-array [4, 5]:

      1. Pivot: 5
      2. Partitioning: Rearrange to get [4, 5] (5 is in its final position).
      3. Recursive Calls:
        • Left: [4] (single element - base case)
        • Right: [] (empty - base case)

    B. Sorting the Right Sub-array [7, 9, 8]:

    1. Pivot: 8
    2. Partitioning: Rearrange to get, for example, [7, 8, 9] (8 is in its final position)
    3. Recursive Calls:
      • Left: [7] (single element - base case)
      • Right: [9] (single element - base case)

  4. Combining the Results:

Since all the sub-arrays have been reduced to single elements or empty arrays (our base cases), and the pivots are all in their correct final positions, the entire array is now sorted!

[1, 2, 3, 4, 5, 6, 7, 8, 9]

If you wish to vizualize all these steps in detail, you may visit this article: Quick Sort Algorithm: Visualization and Animation.

Key Concepts in Action

Now that we’ve seen quick sort in action, let’s understand the important ideas behind it:

  • Divide and Conquer: Quick sort breaks down a big problem (sorting the whole array) into smaller problems (sorting smaller sub-lists). Each of these sub-lists is then solved independently, by using the same algorithm. Once all sub-lists are sorted, we’ll get the full sorted list.

  • Pivot Selection: We need to choose one element (the pivot) to help us split the array. In our example, we simply used the last element each time. The choice of pivot can make the sorting faster or slower.

  • Partitioning: This is where the magic happens! We rearrange elements so smaller ones go before the pivot element and larger ones go after it. After partitioning, the pivot is exactly where it belongs in the final sorted array.

  • Recursion: Quick sort repeats itself on the smaller pieces. It’s like saying, “Now that I’ve put the pivot in the right place, let me sort what’s on the left and what’s on the right using the same method.”

  • When to Stop: The sorting stops when:

    • We have nothing to sort (empty array)
    • We have just one element (already sorted!)

What’s Next?

Now that you have a solid understanding of how quick sort works, you can explore these related topics: