Quick Sort

Quick Sort Algorithm in C++ (Complete Implementation)

IntermediateTopic: Sorting & Searching Programs
Back

C++ Quick Sort Program

This program helps you to learn the fundamental structure and syntax of C++ programming.

Try This Code
#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);
        
        // Recursively sort elements before and after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    cout << "Original array: ";
    printArray(arr, n);
    
    quickSort(arr, 0, n - 1);
    
    cout << "Sorted array: ";
    printArray(arr, n);
    
    return 0;
}
Output
Original array: 64 34 25 12 22 11 90
Sorted array: 11 12 22 25 34 64 90

Understanding Quick Sort

This program teaches you how to implement the Quick Sort algorithm in C++. Quick Sort is a highly efficient divide-and-conquer sorting algorithm that works by selecting a pivot element and partitioning the array around it. It's one of the fastest sorting algorithms in practice and is widely used in real-world applications.

---

1. What This Program Does

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.

---

2. Header File Used

This header provides:

•cout for displaying output
•cin for taking input from the user

---

#include <iostream>

3. Understanding Quick Sort

Algorithm Concept

:

1.

Choose Pivot

: Select an element as pivot (often last element)

2.

Partition

: Rearrange array so pivot is in correct position

•Elements < pivot go to left
•Elements > pivot go to right

3.

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...

---

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

}

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

---

5. 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)

---

6. 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

---

7. 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₂

---

8. 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)

---

9. 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

---

10. return 0;

This ends the program successfully.

---

Summary

•Quick Sort uses divide-and-conquer with pivot-based partitioning.
•Time complexity: O(n log n) average, O(n²) worst case.
•Space complexity: O(log n) for recursive calls.
•Not stable - partitioning can change relative order.
•In-place sorting - modifies original array.
•Pivot selection affects performance significantly.
•Generally faster than Merge Sort in practice due to better cache performance.
•Understanding Quick Sort is essential for efficient sorting algorithms.

This program is fundamental for beginners learning divide-and-conquer algorithms, understanding partitioning, and preparing for advanced algorithm design in C++ programs.

Let us now understand every line and the components of the above program.

Note: To write and run C++ programs, you need to set up the local environment on your computer. Refer to the complete article Setting up C++ Development Environment. If you do not want to set up the local environment on your computer, you can also use online IDE to write and run your C++ programs.

Practical Learning Notes for Quick Sort

This C++ program is part of the "Sorting & Searching Programs" topic and is designed to help you build real problem-solving confidence, not just memorize syntax. Start by understanding the goal of the program in plain language, then trace the logic line by line with a custom input of your own. Once you can predict the output before running the code, your understanding becomes much stronger.

A reliable practice pattern is to run the original version first, then modify only one condition or variable at a time. Observe how that single change affects control flow and output. This deliberate style helps you understand loops, conditions, and data movement much faster than copying full solutions repeatedly.

For interview preparation, explain this solution in three layers: the high-level approach, the step-by-step execution, and the time-space tradeoff. If you can teach these three layers clearly, you are ready to solve close variations of this problem under time pressure.

Next
Heap Sort
Previous
Merge Sort
Next
Heap Sort

Table of Contents