C++ Program for Quick Sort Algorithm

A C++ program for quick sort uses a partition function to divide the array and recursively sorts subarrays with quickSort(arr, low, high) calls.

Examples

Inputarr = {5, 3, 8, 4, 2}, low = 0, high = 4

OutputSorted array: 2 3 4 5 8

Inputarr = {1, 2, 3, 4, 5}, low = 0, high = 4

OutputSorted array: 1 2 3 4 5

Inputarr = {10}, low = 0, high = 0

OutputSorted array: 10

How to Think About It

To sort an array using quick sort, pick a pivot element and rearrange the array so that elements smaller than the pivot come before it and larger ones come after. Then, apply the same process recursively to the parts before and after the pivot until the whole array is sorted.

Algorithm

1

Choose the last element as pivot.

2

Partition the array so elements less than pivot are left, greater are right.

3

Recursively apply quick sort to the left subarray.

4

Recursively apply quick sort to the right subarray.

5

Stop when subarray size is 1 or 0.

Code

cpp

#include <iostream>
using namespace std;

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++;
            swap(arr[i], arr[j]);
        }
    }
    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);
    }
}

int main() {
    int arr[] = {5, 3, 8, 4, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;
    return 0;
}

Output

Sorted array: 2 3 4 5 8 

Dry Run

Let's trace the array {5, 3, 8, 4, 2} through the quick sort code.

1

Initial call

quickSort(arr, 0, 4) with arr = {5, 3, 8, 4, 2}

2

Partitioning

Pivot = 2; after partition arr = {2, 3, 8, 4, 5}, pivot index = 0

3

Left subarray

quickSort(arr, 0, -1) stops (no elements)

4

Right subarray

quickSort(arr, 1, 4) with arr = {3, 8, 4, 5}

5

Partitioning right subarray

Pivot = 5; after partition arr = {3, 4, 5, 8}, pivot index = 3

6

Sort left of pivot

quickSort(arr, 1, 2) with arr = {3, 4}

7

Partitioning left of pivot

Pivot = 4; after partition arr = {3, 4}, pivot index = 2

8

Recursion ends

Subarrays of size 1 or 0 stop recursion

Step	Array State	Pivot	Pivot Index
1	{5, 3, 8, 4, 2}	2	0
2	{2, 3, 8, 4, 5}	5	3
3	{2, 3, 4, 5, 8}	4	2

Why This Works

Step 1: Choosing pivot

The pivot divides the array into smaller and larger parts using partition.

Step 2: Partitioning

Elements less than pivot move left, greater move right, placing pivot in correct position.

Step 3: Recursion

Quick sort repeats on subarrays left and right of pivot until fully sorted.

Alternative Approaches

Lomuto partition scheme

cpp

#include <iostream>
using namespace std;

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++;
            swap(arr[i], arr[j]);
        }
    }
    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);
    }
}

int main() {
    int arr[] = {5, 3, 8, 4, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;
    return 0;
}

This is the classic Lomuto partition; simple but can be less efficient on some inputs.

Hoare partition scheme

cpp

#include <iostream>
using namespace std;

int partition(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;
        swap(arr[i], arr[j]);
    }
}

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

int main() {
    int arr[] = {5, 3, 8, 4, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;
    return 0;
}

Hoare partition is more efficient with fewer swaps but more complex to implement.

Complexity: O(n log n) average, O(n^2) worst time, O(log n) space

Time Complexity

Quick sort divides the array and sorts subarrays recursively. Average case is O(n log n) because each partition splits the array roughly in half. Worst case is O(n^2) when pivot choices are poor, like always smallest or largest element.

Space Complexity

Quick sort uses O(log n) space due to recursion stack. It sorts in place, so no extra arrays are needed.

Which Approach is Fastest?

Hoare partition is often faster due to fewer swaps, but Lomuto is simpler and more common for teaching.

Approach	Time	Space	Best For
Lomuto partition	O(n log n) avg, O(n^2) worst	O(log n)	Simplicity and teaching
Hoare partition	O(n log n) avg, O(n^2) worst	O(log n)	Performance with fewer swaps