Quick Sort in C++

Quick Sort Algorithm in C++ (Complete Implementation).

IntermediateSorting & Searching ProgramsExample 5 of 13

quick-sort.cpp

1#include <iostream>
2using namespace std;
3
4int partition(int arr[], int low, int high) {
5    int pivot = arr[high];
6    int i = low - 1;
7    
8    for (int j = low; j < high; j++) {
9        if (arr[j] < pivot) {
10            i++;
11            swap(arr[i], arr[j]);
12        }
13    }
14    swap(arr[i + 1], arr[high]);
15    return i + 1;
16}
17
18void quickSort(int arr[], int low, int high) {
19    if (low < high) {
20        int pi = partition(arr, low, high);
21        
22        // Recursively sort elements before and after partition
23        quickSort(arr, low, pi - 1);
24        quickSort(arr, pi + 1, high);
25    }
26}
27
28void printArray(int arr[], int n) {
29    for (int i = 0; i < n; i++) {
30        cout << arr[i] << " ";
31    }
32    cout << endl;
33}
34
35int main() {
36    int arr[] = {64, 34, 25, 12, 22, 11, 90};
37    int n = sizeof(arr) / sizeof(arr[0]);
38    
39    cout << "Original array: ";
40    printArray(arr, n);
41    
42    quickSort(arr, 0, n - 1);
43    
44    cout << "Sorted array: ";
45    printArray(arr, n);
46    
47    return 0;
48}

Output

Original array: 64 34 25 12 22 11 90
Sorted array: 11 12 22 25 34 64 90

What's going on

The program sorts an array of integers using the Quick Sort algorithm. For example:

Input array: [64, 34, 25, 12, 22, 11, 90]

Output array: [11, 12, 22, 25, 34, 64, 90]

Quick Sort works by selecting a pivot, partitioning the array so elements smaller than pivot are on the left and larger on the right, then recursively sorting the partitions.

Header File Used

This header provides:

cout for displaying output

cin for taking input from the user

1#include <iostream>

Understanding Quick Sort

Algorithm Concept

Choose Pivot

: Select an element as pivot (often last element)

Partition

: Rearrange array so pivot is in correct position

Elements < pivot go to left

Elements > pivot go to right

Recurse

: Recursively sort left and right partitions

Visual Example

[64, 34, 25, 12, 22, 11, 90]

Pivot: 90 (last element)

Partition: [64, 34, 25, 12, 22, 11] | 90

(all < 90) (pivot)

Recurse on [64, 34, 25, 12, 22, 11]

Pivot: 11

Partition: 11 | [64, 34, 25, 12, 22]

(pivot) (all > 11)

Continue recursively...

Function: partition()

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]);

}

1return i + 1;

How it works

pivot: last element (arr[high])

i: index of smaller element (starts at low - 1)

j: traverses array from low to high - 1

If arr[j] < pivot, increment i and swap

After loop, place pivot at i + 1 (correct position)

Partition Process

(pivot = 90):

[64, 34, 25, 12, 22, 11, 90]

i = -1, j = 0: 64 < 90 → i=0, swap → [64, ...]

j = 1: 34 < 90 → i=1, swap → [64, 34, ...]

j = 2: 25 < 90 → i=2, swap → [64, 34, 25, ...]

...

After loop: [64, 34, 25, 12, 22, 11, 90]

Place pivot: [64, 34, 25, 12, 22, 11, 90] (pivot already at end)

Function: quickSort()

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);

}

How it works

Base case: if low >= high, subarray has 0 or 1 element

Partition: place pivot in correct position, get partition index

Recurse: sort left partition (low to pi-1) and right partition (pi+1 to high)

Understanding Partition

Partition Goal

Place pivot in its final sorted position

All elements < pivot to the left

All elements > pivot to the right

Partition Index (pi)

Returns position where pivot is placed

Left partition: [low, pi - 1]

Right partition: [pi + 1, high]

Pivot at pi is in correct position

Time and Space Complexity

Time Complexity

Best case: O(n log n) - balanced partitions

Average case: O(n log n) - random data

Worst case: O(n²) - pivot always smallest/largest

Space Complexity

: O(log n)

Recursive call stack

Average depth: log n

Worst case: O(n) if unbalanced

Stability

: Not Stable

Swapping during partition can change relative order

Example: [3₁, 3₂, 1] → partition can swap 3₁ and 3₂

When to Use Quick Sort

Best For

Large datasets

Average-case performance critical

In-place sorting needed

General-purpose sorting

Not Recommended For

When worst-case O(n²) is unacceptable

When stability is required

Nearly sorted data (can degrade to O(n²))

Small datasets (overhead of recursion)

Important Considerations

Pivot Selection

This implementation uses last element

Other strategies: first, middle, random, median

Pivot choice affects performance

Partition Balance

Balanced partitions → O(n log n)

Unbalanced partitions → O(n²)

Random pivot helps avoid worst case

Recursive Calls

Tail recursion can be optimized

Iterative version possible

Stack depth depends on partition balance

return 0;

This ends the program successfully.

PreviousMerge Sort NextHeap Sort