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

#define SIZE 1000000

void print_array (int * array)
{	
	int i;
	for (i=0; i< SIZE; i++)
	{
		printf ("%d ", array [i]);
	}
	printf ("\n");
}


int partition (int * array, int left, int right, int element)
{
	int l, r, t;
	
	l = left-1;
	r = right;
	do {
		do {
			l++;
			if (l >= SIZE) break;
		} while (array [l] < element);
		do {
			r--;
			if (r < 0) break;
		} while (array [r] > element);
		if (l < r) {
			t = array [l];
			array [l] = array [r];
			array [r] = t;
			// printf ("Swapped %d %d\n", l, r);
			// print_array (array);
		}
	} while (l < r);
	// l ist Pivotstelle
	t = array [l];
	array [l] = array [right];
	array [right] = t;
	// printf ("Partitoned: %d\n", l);
	// print_array(array);
	return l;
}

void quicksort (int * array, int left, int right)
{
	int p;

	// printf ("quicksorting %d %d\n", left, right);
	// print_array (array);
	if (left < right)
	{
		p = partition (array, left, right, array[right]);
		quicksort (array, left, p-1);
		quicksort (array,p+1, right);
	}
}

int compare (const void *a, const void *b)
{
	if      ((* (int *)a) <  (* (int *)b)) return -1;
	else if ((* (int *)a) >  (* (int *)b)) return 1;
	else return 0;
}


int main()
{
	int i;
	int array [SIZE]={5,1};
	
	srand (10);
	for (i=0; i< SIZE;i++)
	{
		//scanf ("%d", &array[i]);
		array[i] = rand();
	}
	quicksort (array, 0, SIZE-1);
	// qsort (array, (SIZE-1),sizeof(int), &compare);
	// print_array (array);
	return 0;
}