Quick Sort

Pick a pivot

Quick sort picks a pivot and rearranges so everything smaller is on its left and everything bigger on its right. The pivot is then in its final place; sort each side the same way.

Think of it like this: “Everyone shorter than Ravi, stand left; taller, stand right.” Ravi is now in his final spot. Repeat in each group.

#include <iostream>
#include <vector>
using namespace std;

int partitionLomuto(vector<int>& a, int lo, int hi) {
    int pivot = a[hi];               // last item is the pivot
    int i = lo;                      // next spot for a smaller item
    for (int j = lo; j < hi; j++)
        if (a[j] < pivot) swap(a[i++], a[j]);
    swap(a[i], a[hi]);               // pivot goes between the groups
    return i;
}

void quickSort(vector<int>& a, int lo, int hi) {
    if (lo >= hi) return;
    int p = partitionLomuto(a, lo, hi);
    quickSort(a, lo, p - 1);
    quickSort(a, p + 1, hi);
}

int main() {
    vector<int> a = {10, 7, 8, 9, 1, 5};
    quickSort(a, 0, a.size() - 1);
    for (int x : a) cout << x << ' ';
    cout << endl;
    return 0;
}

Output

1 5 7 8 9 10 

Tip: std::nth_element uses the same partition idea to find the k-th smallest item in O(n) on average, without sorting everything.