quicksort.cpp

// Compiled with: g++ -Wall -std=c++14 -pthread

#include <bits/stdc++.h>

using namespace std;

void quick_sort(vector<int> &a, int l, int r) {
    int i = l;
    int j = r;
    int p = (l + r) / 2; // pivot
    while(i <= j) {
        while(a[i] < a[p]) i++;
        while(a[j] > a[p]) j--;
        if(i <= j) {
            swap(a[i], a[j]);
            i++;
            j--;
         }
    }
    if(j > l)
        quick_sort(a, l, j);
    if(i < r)
        quick_sort(a, i, r);
}

int main(){
    vector<int> a = {100, 3, 2, 4, 2, -1, 9};
    quick_sort(a, 0, a.size() - 1);
    for(int &x: a) {
        cout << x << " ";
    }
    cout << "\n";
    return 0;
}