/* partition.c - We write a function that given an integer array a with n 
elements and an integer v, it reorders the elements of a and 
returns a value k such that all elements of a in positions less than k are 
smaller or equal to v, and all elements in a at positions 
greater or equal to k are greater than v.
*/

#include <stdio.h>

/* What is the time complexity of this function */
int partition(int n, int a[n], int v) {
    int low = 0;
    int high = n-1;
    while (low < high) {
	// What is the loop invariant here?
	if (a[low] <= v)
	    low++;
	else {
	    int temp = a[low];
	    a[low] = a[high];
	    a[high] = temp;
	    high--;	
	}
    }
    return low;
}

int main(){
    int a[] = {7,3,8,1,6,3,4,5,0};
    int j;
    for(j=0; j<9; j++)
	printf("\t%d\n", a[j]);
    int v = 4;
    int k = partition(9, a, v);
    printf("v=%d, k=%d\n", v, k);
    for(j=0; j<9; j++)
	printf("\t%d\n", a[j]);
    return 0;
}