#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<stack>
using namespace std;
pair<int, int> quicksort(vector<int>& arr, int l, int r) {
	int index = l;
	int i = l - 1;
	int j = r + 1;
	int tmp = arr[index];
	while (index < j) {
		if (arr[index] == tmp) {
			index++;
		}
		else if (arr[index] < tmp) {
			i++;
			swap(arr[index], arr[i]);
			index++;
		}
		else {
			j--;
			swap(arr[index], arr[j]);
		}
	}
	return make_pair(i, j);
}


void quicksortrecur(vector<int>& arr) {
	stack<pair<int, int>> stk;
	stk.push(make_pair(0,arr.size()-1));
	while (!stk.empty()) {
		pair<int,int> p = stk.top();
		stk.pop();
		pair<int, int> part = quicksort(arr,p.first,p.second);
		if (part.first > p.first) {
			stk.push(make_pair(p.first,part.first));
			
		}
		if (part.second < p.second) {
			stk.push(make_pair(part.second,p.second));
		}
	}
}


void print(vector<int>& arr) {
	for (int i = 0;i < arr.size();i++) {
		cout << arr[i] << '\t';
	}
}
int main() {
	vector<int> arr = { 10,20,5,36,22,51 };
	quicksortrecur(arr);
	print(arr);
	return 0;
}