quicksort

.cpp

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

int partition(vector<int> &v, int low, int high) {
	int pivot = v[low];
	int index = low + 1;
	for (int i = low + 1; i <= high; i++) {
		if (v[i] < pivot) {
			swap(v[i], v[index]);
			index++;
		}
	}
	swap(v[index-1], v[low]);
	return index-1;
}

void quickSort(vector<int> &v, int low, int high) {
	if (low < high) {
		int pivot = partition(v, low, high);
		quickSort(v, low, pivot-1);
		quickSort(v, pivot+1, high);
	}
}

int main() {
	vector<int> v = {4,2,1,5,6};
	quickSort(v, 0, v.size()-1);
	for (auto i : v) {
		cout << i << endl;
	}
    return 0;
}