/* Aufgabe 38 Prakash Punnoor */

class Aufgabe38
{
	public static void main (String[] args)
	{
		/* Testfolge */
		int F[] = {5, 3, 4, 2, 7, -1, 4, -9, 5};
		
		System.out.println("unsortiert: ");
		for (int i = 0; i < F.length; ++i)
			System.out.print(F[i] + " ");
		
		System.out.println("");
		
		quicksort(F);
		
		System.out.println("sortiert: ");
		for (int i = 0; i < F.length; ++i)
		  System.out.print(F[i] + " ");
		
		System.out.println("");
	}
	
	public static void quicksort(int F[])
	{
		qsort(F, 0, F.length - 1);
	}
	
	static void qsort(int F[], int l, int r)
	{
		if (r <= l)
			return;
		
		/* Wir halten die Möglichkeit offen, das Pivotel.
		beliebig zu wählen, und schieben es ans Ende, um den
		Alg. gemäß Vorlesung anwenden zu können */
		int pivot_index = get_pivot_index(F, l, r);
		int pivot = F[pivot_index];
		vertausche(F, pivot_index, r);
		
		int i = l - 1;
		int j = r;
		
		do {
			/* Pivot ist am Ende, also Stopper */
			do { ++i; } while (F[i] < pivot);
			/* Wir haben keinen Stopper... */
			do { --j; } while (F[j] > pivot  &&  j > l);
			if (i < j)
				vertausche(F, i, j);
		} while(j > i);
		vertausche(F, i, r);
		
		qsort(F, l, i - 1);
		qsort(F, i + 1, r);
	}
	
	static int get_pivot_index(int F[], int l, int r)
	{
		/* Hier kann man experimentieren... */
		return r;
	}
	
	static void vertausche(int F[], int a, int b)
	{
		int temp = F[a];
		F[a] = F[b];
		F[b] = temp;
	
	}
}