#include <stdio.h>
#include <windows.h>
#define SIZE 1000000
void quicksort(int*, int, int);
void swap(int*, int, int);
int main() {
	srand(time(NULL));
	int input[SIZE];
	printf("ALIVE\n");
	long int i;
	for(i = 0;i<SIZE-1; i++) {
		input[i] = rand();
	}
	LARGE_INTEGER before, after;
	QueryPerformanceCounter(&before);
	quicksort(input, 0, SIZE);
	QueryPerformanceCounter(&after);
	printf("Time: %d\n", (after.QuadPart - before.QuadPart));
/*	for(i = 0;i < SIZE; i++) {
		printf(i+1==SIZE?"%d":"%d, ", input[i]);
	}*/
	return 0;
}
void quicksort(int* input, int first, int last) {
	if(first > last) {
		return;
	 }
	 int il, ir, pivot; // index left, index right
	 il = first;
	 ir = last;
	 pivot = input[first];
	 while(ir > il) {	
		while(input[il] <= pivot && il <= last && ir > il) {
			il++;
		}
		while(input[ir] > pivot && ir >= first && ir >= il) {
			ir--;
		}
		if(ir > il) {
			swap(input, il, ir);
		}
	 }
	 swap(input, first, ir);	 
	 quicksort(input, first, ir - 1); 
	 quicksort(input, ir + 1, last); 
}

void swap(int* input, int first, int last)  {
	int temp = input[first]; 
	input[first] = input[last];    
	input[last] = temp;
}