Quick Sort Algorithm in DSA C++

Mental Model

Quick Sort picks a pivot and arranges elements so smaller ones go left and bigger ones go right, then sorts each side the same way.

Analogy: Imagine sorting books on a shelf by picking one book as a reference, putting all smaller books to the left and bigger books to the right, then repeating this for each side until all books are sorted.

Array before sorting:
[ 8, 3, 7, 6, 2 ]
Pivot chosen -> 2
Partitioning around pivot:
[ 2, 3, 7, 6, 8 ]
Left side ↑
Right side ↑

Dry Run Walkthrough

Input: array: [8, 3, 7, 6, 2]

Goal: Sort the array in ascending order using Quick Sort

Step 1: Choose pivot as last element 2, partition array around pivot

[8, 3, 7, 6, 2] -> pivot=2
Partitioning: elements < 2 to left, others right

Why: Pivot divides array into smaller and larger parts

Step 2: Swap 2 with first element 8 to place pivot correctly

[2, 3, 7, 6, 8]
Pivot 2 is now at correct position index 0

Why: Pivot must be at its final sorted position

Step 3: Recursively quick sort left subarray [] (empty) and right subarray [3,7,6,8]

Left: []
Right: [3,7,6,8]

Why: Sort smaller parts separately

Step 4: Choose pivot 8 in right subarray, partition around 8

[3,7,6,8]
Pivot=8
All elements < 8, so pivot stays at end

Why: Pivot placement divides array further

Step 5: Recursively quick sort left subarray [3,7,6] and right subarray []

Left: [3,7,6]
Right: []

Why: Continue sorting smaller parts

Step 6: Choose pivot 6 in left subarray, partition around 6

[3,7,6]
Pivot=6
After partition: [3,6,7]

Why: Pivot placed at correct position

Step 7: Recursively quick sort left subarray [3] and right subarray [7]

Left: [3]
Right: [7]

Why: Single elements are sorted

Step 8: All subarrays sorted, combine results

[2,3,6,7,8]

Why: Final sorted array

Result:

[2, 3, 6, 7, 8] -- sorted array

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

// Partition function places pivot at correct position
int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high]; // choose last element as pivot
    int i = low - 1; // index of smaller element
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++; // move smaller element index forward
            swap(arr[i], arr[j]); // place smaller element left
        }
    }
    swap(arr[i + 1], arr[high]); // place pivot after smaller elements
    return i + 1; // return pivot index
}

// QuickSort recursive function
void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high); // partition array
        quickSort(arr, low, pi - 1); // sort left subarray
        quickSort(arr, pi + 1, high); // sort right subarray
    }
}

int main() {
    vector<int> arr = {8, 3, 7, 6, 2};
    quickSort(arr, 0, arr.size() - 1);
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

int pivot = arr[high];

select pivot as last element

for (int j = low; j < high; j++) { if (arr[j] < pivot) { i++; swap(arr[i], arr[j]); } }

move elements smaller than pivot to left side

swap(arr[i + 1], arr[high]);

place pivot after smaller elements

int pi = partition(arr, low, high);

partition array and get pivot index

quickSort(arr, low, pi - 1);

recursively sort left subarray

quickSort(arr, pi + 1, high);

recursively sort right subarray

Output

2 3 6 7 8 

Complexity Analysis

Time: O(n log n) average case because each partition divides array roughly in half and sorting happens recursively

Space: O(log n) due to recursion stack in average case

vs Alternative: Compared to Bubble Sort's O(n^2), Quick Sort is much faster on average but worst case is O(n^2) if pivot choices are poor

Edge Cases

empty array

function returns immediately without changes

DSA C++

if (low < high) {

array with one element

function returns immediately as array is already sorted

DSA C++

if (low < high) {

array with all equal elements

partition places pivot but no swaps needed, recursion continues until base cases

DSA C++

if (arr[j] < pivot) {

When to Use This Pattern

When you need to sort an array efficiently and can pick a pivot to divide and conquer, use Quick Sort because it sorts in place and is fast on average.

Common Mistakes

Mistake: Not updating the index of smaller elements correctly in partition
Fix: Increment i only when a smaller element is found and swap it with current element

Mistake: Forgetting to swap pivot to its correct position after partitioning
Fix: Swap pivot with element at i+1 after partition loop

Mistake: Calling quickSort with wrong subarray boundaries causing infinite recursion
Fix: Call quickSort with low to pi-1 and pi+1 to high correctly

Summary

Quick Sort sorts an array by dividing it around a pivot and sorting subarrays recursively.

Use Quick Sort when you want an efficient in-place sorting algorithm with average O(n log n) time.

The key insight is partitioning the array so the pivot is in its final place, then sorting left and right parts separately.