Quick Sort - Code Scholars Tutoring | Learn Coding with Code Scholars

Quick Sort: A Step-by-Step Guide

Quick sort is a powerful divide‐and‐conquer algorithm that efficiently sorts an array by leveraging partitioning around a special element called the pivot. In this tutorial, we’ll walk through how quick sort works using an example, show its recursive nature, and provide an improved visual diagram to make the steps clear.

Why Quick Sort?

Divide and Conquer: Like merge sort, quick sort splits the problem and solves smaller instances.
Speed: On average, quick sort runs in O(nlog⁡n)O(n \log n)O(nlogn) time. It’s often faster than other O(nlog⁡n)O(n \log n)O(nlogn) sorts in practice due to good cache performance and average-case efficiency.
In-Place: Unlike merge sort, quick sort can be done in-place (requiring only a small amount of additional memory).

The Quick Sort Algorithm in Three Phases

1. Divide (Partition)

Choose a pivot. Often, we pick the rightmost element in the subarray as the pivot.
Partition the subarray so that every element less than or equal to the pivot ends up to its left, and every element greater than the pivot ends up to its right.

2. Conquer

Recursively apply quick sort to the subarray to the left of the pivot (elements smaller or equal to the pivot).
Recursively apply quick sort to the subarray to the right of the pivot (elements greater than the pivot).

3. Combine

Do nothing! Once each side has been sorted and placed around the pivot, the entire subarray (and eventually the entire array) will be sorted.

Walking Through an Example

Let’s say we have the following array (with indices from 0 to 9):

iniCopy code[9, 7, 5, 11, 12, 2, 14, 3, 10, 6]
  p=0                            r=9

First Pivot = 6 (rightmost element)
- Partition around 6:
  - Move all elements ≤ 6 to the left side, and all elements > 6 to the right side.
  - One possible partitioning result: [5,2,3, 6, 12,7,14,9,10,11] [5, 2, 3,\, 6,\, 12, 7, 14, 9, 10, 11][5,2,3,6,12,7,14,9,10,11] Here, 6 ends up at index 3.
- Now, the array splits into two subarrays around the pivot 6:
  - Left subarray: [5, 2, 3] (indices 0..2)
  - Right subarray: [12, 7, 14, 9, 10, 11] (indices 4..9)
Sort the Left Subarray [5, 2, 3]
- Pivot = 3 (rightmost element).
- Partition around 3 ⇒ [2, 3, 5].
- After partitioning:
  - Left side of pivot: [2]
  - Right side of pivot: [5]
  - Both are base cases (single elements), so no further sorting is needed.
Sort the Right Subarray [12, 7, 14, 9, 10, 11]
- Pivot = 11 (rightmost element).
- Partition around 11 ⇒ One possible partitioning: [7,9,10, 11, 14,12] [7, 9, 10,\, 11,\, 14, 12][7,9,10,11,14,12] (Pivot 11 ends up at index 3 relative to this subarray.)
- Subarrays are [7, 9, 10] (left of pivot) and [14, 12] (right of pivot).
  - Sort [7, 9, 10]: it’s already in correct order after partitioning around 10 (for instance), so it stays [7, 9, 10].
  - Sort [14, 12]: pivot = 12 ⇒ [12, 14].

Putting it all together after the recursion finishes:

lessCopy codeLeft side:      [2, 3, 5]
Pivot (level 1):      6
Right side:     [7, 9, 10, 11, 12, 14]

Which is:

csharpCopy code[2, 3, 5, 6, 7, 9, 10, 11, 12, 14]

Fully sorted!