Quick Sort — Algorithm Animation

What does it solve?

Sorts an array by picking a pivot element and partitioning the array around it: everything smaller goes left, everything larger goes right. The pivot lands in its final sorted position.

The two resulting sub-arrays are then sorted recursively using the same process — divide and conquer — until each sub-array has zero or one element.

The core idea (Lomuto partition)

// pivot = arr[high], i = boundary
i = low - 1
for j = low to high-1:
if arr[j] < pivot:
i++; swap(arr[i], arr[j])
swap(arr[i+1], arr[high])

Complexity

Time complexity

O(N log N)

Average case with balanced partitions. Worst case is O(N²) when the pivot repeatedly lands at an extreme, e.g. already-sorted input with a naive pivot choice.

Space complexity

O(log N)

In-place partitioning — space is only used by the recursion call stack, which is O(N) in the worst case.

Examples & edge cases

Live animation

Pivot Comparing (j) Boundary (i) Outside current range Final position

depth: — range: —

Step — of —

Pivot value

—

at index —

Comparing (j)

—

Boundary (i)

—

Swaps so far

—

total

Select an example and press Play to start.

✓ Sorted

Speed Medium

Step-by-step table

Step	Range	Pivot	i	j	Action	Array state

C++ implementation (Lomuto partition)

quick_sort.cpp

#include <bits/stdc++.h>
using namespace std;

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high];      // choose last element as pivot
    int i = low - 1;          // boundary of "less than pivot" region

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);  // place pivot in final position
    return i + 1;
}

void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);   // left of pivot
        quickSort(arr, pi + 1, high);  // right of pivot
    }
}

int main() {
    vector<int> arr = {10, 80, 30, 90, 40, 50, 70};
    quickSort(arr, 0, arr.size() - 1);

    for (int x : arr) cout << x << " ";
    cout << "\n";
    return 0;
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars