C/C++ Algorithms

Quick Sort

Quick sort places a pivot in its final position, then recursively sorts the two partitions.

What is Quick Sort?

Quick sort places a pivot in its final position, then recursively sorts the two partitions.

Partition values around a pivot.

Important points

Test empty, single-element, duplicate, and already sorted inputs.
Separate correctness from optimization.
Use the standard library in production unless a custom implementation is justified.

Quick Sort visualizer

O(n log n)

Use Play or Step to follow each comparison and data movement.

C and C++ code examples

Run code →

main.c

#include <stdio.h>

void swap(int *left, int *right) {
    int temporary = *left;
    *left = *right;
    *right = temporary;
}

int partition(int *values, int low, int high) {
    int pivot = values[high];
    int boundary = low;
    for (int scan = low; scan < high; ++scan) {
        if (values[scan] < pivot) {
            swap(&values[boundary++], &values[scan]);
        }
    }
    swap(&values[boundary], &values[high]);
    return boundary;
}

void quick_sort(int *values, int low, int high) {
    if (low >= high) return;
    int pivot = partition(values, low, high);
    quick_sort(values, low, pivot - 1);
    quick_sort(values, pivot + 1, high);
}

int main(void) {
    int values[] = {9, 4, 7, 3, 10, 5};
    quick_sort(values, 0, 5);
    for (int index = 0; index < 6; ++index) {
        printf("%d ", values[index]);
    }
}

Expected output

3 4 5 7 9 10

C++

Run code →

main.cpp

#include <algorithm>
#include <iostream>
#include <vector>

template<class Iterator>
void quick_sort(Iterator first, Iterator last) {
    if (last - first < 2) return;
    auto pivot = *(last - 1);
    auto middle = std::partition(first, last - 1,
        [pivot](int value) { return value < pivot; });
    std::iter_swap(middle, last - 1);
    quick_sort(first, middle);
    quick_sort(middle + 1, last);
}

int main() {
    std::vector values{9, 4, 7, 3, 10, 5};
    quick_sort(values.begin(), values.end());
    for (int value : values) {
        std::cout << value << ' ';
    }
}

Expected output

3 4 5 7 9 10

C and C++ comparison

Average time is O(n log n), but poor pivots can produce O(n²). The C++ example uses std::partition to express the partition step while retaining the algorithm.

Loops, pointers, lengths, and temporary buffers are written explicitly.

C++

Iterators and standard algorithms separate operations from container representation.

Practice exercises

Run both versions, then modify them to observe the different language guarantees.

Trace each comparison on paper.
Test duplicates and extreme values.
Benchmark the custom implementation against the standard library.