import java.util.Random;
public class Aufgaben
{
	public static void main(String[] args)
	{
/**
		int Feld_Anzahl_der_Elemente[] = {10_000,20_000,40_000,80_000,160_000};
		for(int i = 0; i < Feld_Anzahl_der_Elemente.length; ++i)
		{
			int laenge = Feld_Anzahl_der_Elemente[i];
			int Feld_Quicksort[] = new int [laenge];
			int Feld_Insertionsort[] = new int[laenge];
			erzeugen(Feld_Insertionsort, 1000);
			kopieren(Feld_Insertionsort, Feld_Quicksort); // Das zweite ist das in das kopiert werden soll
			insertionsort(Feld_Insertionsort, laenge);
			long begin = System.currentTimeMillis();
			quicksort(Feld_Quicksort, 0, Feld_Quicksort.length-1);
			long end = System.currentTimeMillis();
			System.out.println("Quicksort: "+ laenge + " : " + (end-begin) + "ms");
			System.out.println();
		}
	*/
		int Feld_Quicksort_1Opt[] = new int [10];
		erzeugen(Feld_Quicksort_1Opt, 20);

//		Erste Optimierung Quicksort
		ausgeben(Feld_Quicksort_1Opt);
		quicksort(Feld_Quicksort_1Opt, 0, Feld_Quicksort_1Opt.length-1,0);
		ausgeben(Feld_Quicksort_1Opt);
		System.out.println();
	}

	static public void kopieren(int[] feld, int[] feld1)
	{
		for(int i = 0; i < feld.length; ++i)
		{
			feld1[i] = feld[i];
		}
	}

	static public void erzeugen(int[] feld, int max)
	{
		Random r = new Random();
		for(int i = 0; i < feld.length;++i)
		{
			feld[i] = r.nextInt(max)+1;
		}
	}

	static public void ausgeben(int[] feld)
	{
		for(int i = 0; i < feld.length;++i)
		{
			System.out.print(feld[i] + " ");
		}
		System.out.println();
	}

	static public void insertionsort(int[] feld, int a)
	{
		long begin = System.currentTimeMillis();
		for(int i = 1; i < feld.length;++i)
		{
			int temp = feld[i];
			int j = i-1;
			while(j>=0 && feld[j] > temp)
			{
				feld[j+1] = feld[j];
				--j;
			}
			feld[j+1] = temp;
		}
		long end = System.currentTimeMillis();
		System.out.println("Insertionsort: "+a + " : " + (end-begin) + "ms");
	}

	static void quicksort(int a[], int l, int r)
	{
		int v, i, j , t;

		if (r > l)
		{
			v = a[r];
			i = l-1;
			j = r;
			for (;;)
			{
				while (a[++i] < v) ;
				while (a[--j] > v) ;
				if (i >= j)
					break;
				t = a[i];
				a[i] = a[j];
				a[j] = t;
			}
			t = a[i];
			a[i] = a[r];
			a[r] = t;
			quicksort(a, l, i-1);
			quicksort(a, i+1, r);
		}
	}

	//	 Erste Optimierung
	static void quicksort(int a[], int l, int r, int h)
	{
		int v, i, j , t;

		if (r > l)
		{
			v = pivot_element(a[r], a[l], a[(a.length / 2)]);
			i = l-1;
			j = r;
			for (;;)
			{
				while (a[++i] < v) ;
				while (a[--j] > v) ;
				if (i >= j)
					break;
				t = a[i];
				a[i] = a[j];
				a[j] = t;
			}
			t = a[i];
			a[i] = a[r];
			a[r] = t;
			quicksort(a, l, i-1,0);
			quicksort(a, i+1, r,0);
		}
	}

	static int pivot_element(int a, int b, int c)
	{
		int temp[] = {a,b,c};
		insertionsort(temp);
		return temp[1];
	}

	static public void insertionsort(int[] feld)
	{
		for(int i = 1; i < feld.length;++i)
		{
			int temp = feld[i];
			int j = i-1;
			while(j>=0 && feld[j] > temp)
			{
				feld[j+1] = feld[j];
				--j;
			}
			feld[j+1] = temp;
		}
	}
}