#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <sys/time.h>

#define INPUT_SIZE	14


void quicksort (int l[], int low, int high)
{
	int pivotpoint;

	if (high > low)
	{
		pivotpoint=partition(l, low, high, pivotpoint);
		quicksort(l, low, pivotpoint);
		quicksort(l, pivotpoint+1, high);
	}
}

int partition (int l[], int low, int high, int pivotpoint)
{
	int i,j;
	int pivotitem;
	int temp;

	pivotitem=l[low];
	j=low;
	
	for (i=low+1; i<high; i++)
	{
		if(l[i]<pivotitem)
		{
			j++;
			temp=l[i];
			l[i]=l[j];
			l[j]=temp;
		}
	}
	
	pivotpoint=j;

        temp=l[low];
        l[low]=l[pivotpoint];
        l[pivotpoint]=temp;

	return pivotpoint;
}


int main(void)
{
	long int i, j;
	time_t *now;

	int inputs[]={3,2,6,90,12,32,1,2,2,3,4,1,99,99};;

	struct timeval start_time, stop_time;
	double en, st;
	double microsec = 1000000.0;

        srand(getpid());
//	for (i=0; i<INPUT_SIZE; i++)
  //              inputs[i]=rand();

	
	for (i=0; i<INPUT_SIZE; i++)
		printf("%d, ", inputs[i]);
	printf("\n");
	gettimeofday(&start_time, (struct timezone *) 0);
	
	quicksort(inputs, 0, INPUT_SIZE);

	for (i=0; i<INPUT_SIZE; i++)
                printf("%d, ", inputs[i]);
        printf("\n");
	gettimeofday(&stop_time, (struct timezone *)0);

	st = start_time.tv_sec + (start_time.tv_usec/microsec);
        en = stop_time.tv_sec + (stop_time.tv_usec/microsec);
	printf("real time: %f\n", en-st);

	return 0;
}