Quick Sort in C++ — Full Guide for Beginners

Quick Sort is a divide and conquer algorithm. It’s famous for being fast in practice, with an average time complexity of O(n log n) and very low memory overhead compared to Merge Sort.

In this post, we’ll cover:

• How Quick Sort works
• Lomuto Partition Scheme (Simple)
• Hoare Partition Scheme (Efficient)
• 3-Way Quick Sort (Handles duplicates well)
• Step-by-step examples
• Code in C++
• Comparison of all variations
• Practice questions

---

How Quick Sort Works

1. Choose a pivot element.
2. Partition the array: place all elements less than pivot to the left, greater to the right.
3. Recursively apply this to the left and right sub-arrays.

Visual Example:

Original:
[8, 3, 1, 7, 0, 10, 2]

• Choose pivot = 2
• Partition: [1, 0] [2] [8, 3, 7, 10]
• Recurse on both sides

---

Lomuto Partition Scheme (Easy to Code)

How it Works:

• Picks the last element as the pivot
• Moves elements smaller than pivot to the front

Code:

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
  
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

Example:

int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr)/sizeof(arr[0]);
quickSort(arr, 0, n - 1);

Output: [1, 5, 7, 8, 9, 10]

---

Hoare Partition Scheme (Faster in Practice)

Differences:

• Picks the first element as pivot
• Uses two indices moving inward
• Usually makes fewer swaps

Code:

int hoarePartition(int arr[], int low, int high) {
    int pivot = arr[low];
    int i = low - 1, j = high + 1;

    while (true) {
        do { i++; } while (arr[i] < pivot);
        do { j--; } while (arr[j] > pivot);

        if (i >= j) return j;
        std::swap(arr[i], arr[j]);
    }
}

void quickSortHoare(int arr[], int low, int high) {
    if (low < high) {
        int pi = hoarePartition(arr, low, high);
        quickSortHoare(arr, low, pi);
        quickSortHoare(arr, pi + 1, high);
    }
}

Note:

• Safer for large datasets
• Slightly harder to implement, but performs better on average

---

3-Way Quick Sort (Dutch National Flag)

Why use it?

If your array has lots of duplicate values, normal Quick Sort wastes time re-sorting equal elements.

Strategy:

Partition into three parts:

• Less than pivot
• Equal to pivot
• Greater than pivot

Code:

void quickSort3Way(int arr[], int low, int high) {
    if (low >= high) return;

    int lt = low, gt = high;
    int pivot = arr[low];
    int i = low + 1;

    while (i <= gt) {
        if (arr[i] < pivot)
            std::swap(arr[lt++], arr[i++]);
        else if (arr[i] > pivot)
            std::swap(arr[i], arr[gt--]);
        else
            i++;
    }

    quickSort3Way(arr, low, lt - 1);
    quickSort3Way(arr, gt + 1, high);
}

Use Case:

int arr[] = {4, 5, 4, 3, 4, 2, 1, 4};
int n = sizeof(arr)/sizeof(arr[0]);
quickSort3Way(arr, 0, n - 1);

Output: [1, 2, 3, 4, 4, 4, 4, 5]

---

Comparison of Quick Sort Variants

Variant	Pivot Choice	Stability	Swaps	Best for
Lomuto	Last	No	More	Simpler, educational
Hoare	First	No	Fewer	Better performance, fewer swaps
3-Way	Any	No	Efficient	Arrays with many duplicate values

---

Time & Space Complexity

Case	Time	Space
Best	O(n log n)	O(log n)
Average	O(n log n)	O(log n)
Worst	O(n²)	O(log n) (recursive calls)

Worst case happens when pivot is always the smallest or largest element (e.g., sorted input + bad pivot choice).

---

Practice Questions

1. Implement Quick Sort using Lomuto partitioning on {9, 4, 7, 3, 10, 2}.
2. Explain the difference in output between Hoare and Lomuto on the same input.
3. Why is 3-way quicksort faster when there are many duplicates?
4. Modify the Lomuto code to print the array after each partition step.
5. What happens to the time complexity if the array is already sorted?

---

📌 Final Notes

Quick Sort is a fundamental algorithm not just in theory but also in real-world systems (like C++ STL sort() under the hood). While its worst-case time complexity is O(n²), smart pivot strategies and 3-way partitioning make it extremely efficient in practice.

Mastering Quick Sort gives you:

• A strong grasp of divide-and-conquer
• Deeper understanding of recursion and partitioning
• A foundation for studying advanced variants (like IntroSort)