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

void printVector(vector<int> toPrint){
	for(int i = 0; i < toPrint.size(); i++){
		if (i != 0){
			cout << ", ";
		}
		cout << toPrint[i];
	}
	cout << endl;
}


int HoarePartition(vector<int> & in){
	int startIndex = 0; 
	int stopIndex = in.size()-1;
	int pivot = in[ startIndex ];

	cout << "=== Before Partition ===" <<endl;
	printVector(in);

	while (true){
		while ( in[ startIndex ] <= pivot ){
			startIndex++;
		}
		while ( in[ stopIndex ] > pivot ){
			stopIndex--;
		}
		if( startIndex < stopIndex ){
			// swap!
			int swapCup = in[ startIndex ];
			in[ startIndex ] = in[ stopIndex ];
			in[ stopIndex ] = swapCup;
		}
		else{
			cout << "=== After Partition ===" << endl;
			printVector(in);
			return stopIndex;
		}
	}

}


int main() {
	vector<int> test;
	
	test.push_back(5);
	test.push_back(9);
	test.push_back(8);
	test.push_back(4);
	test.push_back(1);
	test.push_back(2);
	
	HoarePartition(test);
	return 0;
}