//============================================================================
// Name        : quiz3.cpp
// Author      : Christos Choutouridis
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================



int v[] = {
	3, 10, 8, 2, 7, 1, 5, 9, 6, 4
};


void swap (int i, int j) {
	int t = v[i];
	v[i] = v[j];
	v[j] = t;
}

// partition(int f, int l) : permutes the values in vector v[]
//   between positions f and l, using as pivot the element v[l], such
//   that
//     f <= i < p ==> v[i] <= v[p]
//     p < i <= l ==> v[p] <  v[i]
//   The function returns the position p of the pivot.
int partition(int f, int l) {
	int pivot = v[l];       	// element v[l] is the pivot
	int i = f;                  // i points to the beginning of the vector

	// loop over vector
	for (int j = f; j < l; j++)
		if (v[j] < pivot)       // element smaller than pivot
			swap(i++,j);        // swap it with position pointed by i

	swap(i, l );                // swap pivot to its correct position
	return (i);                 // return pivot's position
}

// qsort(int f, int l) : sorts the elements of v[] between positions f:l
void qsort(int f, int l) {
	int pivot;
	if (f < l) {
		pivot = partition(f, l);

		qsort(f, pivot - 1);  	// Before pi
		qsort(pivot + 1, l); 	// After pi
	}
}


int main() {
	int n = 10;

	qsort (0, 9);
	return 0;
}