Algorithms & STL

C++ QuickSort Algorithm (Lomuto & Hoare Partitioning)

Implement the high-performance QuickSort divide-and-conquer sorting algorithm in C++ using in-place median/pivot partitioning.

C++ Source Code

Editable code sample with line numbers

C++

#include <iostream>
#include <vector>
#include <utility>

// Lomuto partition scheme
int partition(std::vector<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(std::vector<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);
    }
}

void printVector(const std::vector<int>& arr) {
    for (int val : arr) {
        std::cout << val << " ";
    }
    std::cout << "\n";
}

int main() {
    std::vector<int> numbers = {64, 25, 12, 22, 11, 90, 45, 33};

std::cout << "Original vector: ";
    printVector(numbers);

quickSort(numbers, 0, static_cast<int>(numbers.size()) - 1);

std::cout << "Sorted vector:   ";
    printVector(numbers);

return 0;
}

Expected Output

When this program is compiled and executed, the terminal outputs:

Original vector: 64 25 12 22 11 90 45 33 
Sorted vector:   11 12 22 25 33 45 64 90

How the Code Works

QuickSort selects a pivot element (here arr[high]) and partitions the array such that all elements smaller than the pivot are placed before it, and all greater elements are placed after it. It recursively repeats the process on the left and right subarrays.

Time Complexity

O(N log N) average, O(N²) worst-case

Space Complexity

O(log N) call stack memory

Key Takeaways & Best Practices

QuickSort is an in-place sort requiring no secondary array allocations.
std::swap() performs move semantics in modern C++.

Master C++ with ZenCompiler

Practice in our high-performance cloud container IDE with multi-file support, interactive terminal STDIN, real-time memory visualizer, and structured lessons.

Related C++ Examples

Data Structures & STL

O(1) for both get and put

C++ LRU Cache (std::list & std::unordered_map)

Implement a high-performance LRU Cache in C++ using std::list for double-linked list ordering and std::unordered_map for O(1) key lookups.

Runnable Code

View Code

Trees & Strings

O(L) for Insert, Search, and StartsWith

C++ Trie (Prefix Tree) Implementation

Build an efficient Prefix Tree (Trie) in C++ supporting fast word insertion, full match search, and prefix matching.

C++ Binary Search (Custom Implementation & std::binary_search)

Implement a template-based binary search algorithm in C++ and compare it with the Standard Template Library (STL) algorithms std::binary_search and std::lower_bound.

Runnable Code

View Code

C++ QuickSort Algorithm (Lomuto & Hoare Partitioning)

C++ Source Code

Expected Output

How the Code Works

Key Takeaways & Best Practices

Master C++ with ZenCompiler

Related C++ Examples

C++ LRU Cache (std::list & std::unordered_map)

C++ Trie (Prefix Tree) Implementation

C++ Binary Search (Custom Implementation & std::binary_search)

Platform & Tools

Account

Company & Help

Legal & Policies

C++ QuickSort Algorithm (Lomuto & Hoare Partitioning)

C++ Source Code

Expected Output

How the Code Works

Key Takeaways & Best Practices

Master C++ with ZenCompiler

Related C++ Examples

C++ LRU Cache (std::list & std::unordered_map)

C++ Trie (Prefix Tree) Implementation

C++ Binary Search (Custom Implementation & std::binary_search)