#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void quick(int *, int, int);

#define N 10


int  main(void){
	int a[N] = {0};
	int k = 0;

	for (k = 0; k < N ; k++) {
		printf("Input a number: ");
		scanf("%d", &a[k]);
	}

	printf("before: ");
	for (k = 0; k < N; k++) {
		printf("%4d", a[k]);
	}
	printf("\n");

	quick(a, 0, N - 1);
	
	printf("after:  ");
	for (k = 0; k < N; k++) {
		printf("%4d", a[k]);
	}
	printf("\n");
}

void check(int a[], int left, int right, int p, int center) {
	int i = 0;
	printf("(%d, %d) pivot: %d, center: %d\n", left, right, p, center);
	for (i = 0; i < N; i++) {
		printf("%4d", a[i]);
	}
	printf("\n");
}

int pivot(int a[], int left, int right) {
	return left;
}

int swap(int *x, int *y) {
	int t = *x;
	*x = *y;
	*y = t;
}

int partition(int a[], int left, int right, int p) {

int i=left,j=right; 

    while(i<=j){
      while(i<=right && a[i]<p)  i++;

      while(j>=left && a[j]>p) j--;

      if(i<=j){
      swap(&a[i],&a[j]);
      	i++;
      	j--;
    }
  }

return i;
}




void quick(int a[], int left, int right) {

if(left>=right) return;

int p = pivot(a, left, right);


int center = partition(a, left, right, a[p]);
	check(a, left, right, p, center);
	quick(a, left, center-1);
	quick(a, center, right);

}