import java.util.Random;

public class sortieren {

	public static void main(String[] args)
	{
		int length = 10;
		int field[] = new int [length];
		int field1[] = new int[length];
		int field2[] = new int[length];
		int field3[] = new int[length];
		int field4[] = new int[length];

		String arr [] = new String[length];
		String arr1 [] = new String[length];
		String arr2 [] = new String[length];
		String arr3 [] = new String[length];

		//Int

		erzeugen(field, 50);
		kopieren(field, field1, field2, field3, field4);
		ausgeben(field);

		System.out.println("Quicksort R");
		quicksort_rechts_Pivot(field,0,field.length - 1);
		ausgeben(field);

		System.out.println("Quicksort L");
		quicksort_Links_Pivot(field1,0,field1.length - 1);
		ausgeben(field1);

		System.out.println("Quicksort M");
		quicksort_mitte(field2,0,field2.length - 1);
		ausgeben(field2);

		System.out.println("Quicksort RLM");
		quicksort_rechtsLinksMitteMedian_Pivot(field3,0,field3.length - 1);
		ausgeben(field3);

		System.out.println();
		System.out.println("String");
		System.out.println();

		//String
		erzeugen(5,arr);
		kopieren(arr, arr1, arr2, arr3);
		ausgeben(arr);

		System.out.println("Quicksort R");
		quicksort_rechts_Pivot(arr,0,arr.length - 1);
		ausgeben(arr);

		System.out.println("Quicksort L");
		quicksort_Links_Pivot(arr1,0,arr1.length - 1);
		ausgeben(arr1);

		System.out.println("Quicksort M");
		quicksort_mitte(arr2,0,arr2.length - 1);
		ausgeben(arr2);

		System.out.println("Quicksort RLM");
		quicksort_rechtsLinksMitteMedian_Pivot(arr3,0,arr3.length - 1);
		ausgeben(arr3);

	}

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

	static public void kopieren(String[] arr, String[] arr1, String[] arr2, String[] arr3)
	{
		for(int i = 0; i < arr.length; ++i)
		{
			arr1[i] = arr[i];
			arr2[i] = arr[i];
			arr3[i] = arr[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 void quicksort_rechts_Pivot(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 (j > 0 && 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_rechts_Pivot(a, l, i-1);
			quicksort_rechts_Pivot(a, i+1, r);
		}
	}

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

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


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

		if (r > l)
		{
			int temp = a[((r+1)-l)/2];
			t = temp;
			temp = a[r];
			a[r] = temp;

			v = a[r];
			i = l-1;
			j = r;
			for (;;)
			{
				while (a[++i] < v) ;
				while (j > 0 && 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_mitte(a, l, i-1);
			quicksort_mitte(a, i+1, r);
		}
	}

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

		if (r > l)
		{
			int temp = median(a[l], a[r], a[((r+1)-l)/2]);
			if(temp == a[l])
			{
				t = a[l];
				a[l] = a[r];
				a[r] = t;

			}

			if(temp == a[((r+1)-l)/2])
			{
				t = a[((r+1)-l)/2];
				a[((r+1)-l)/2] = a[r];
				a[r] = t;

			}

			v = a[r];
			i = l-1;
			j = r;
			for (;;)
			{
				while (a[++i] < v) ;
				while (j > 0 && 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_rechtsLinksMitteMedian_Pivot(a, l, i-1);
			quicksort_rechtsLinksMitteMedian_Pivot(a, i+1, r);
		}
	}

	public static int median(int x, int y, int z)
	{
		return x < y ? y < z ? y : x < z ? z : x : y < z ? x < z ? x : z : y;
	}

	//String Methoden

	static String allowedChars ="0123456789abcdefghijklmnopqrstuvwxyz";

	private static String generateRandomString(String allowedChars, Random random, int laenge)
	{
		int max = allowedChars.length();
		StringBuffer buffer = new StringBuffer();
		for (int i=0; i<laenge; i++)
		{
			int value = random.nextInt(max);
			buffer.append(allowedChars.charAt(value));
		}
		return buffer.toString();
	}

	static public void erzeugen(int stringlaenge,String[] arr)
	{
		Random random = new Random();
		for (int i=0; i<arr.length; i++)
		{
			arr[i] = generateRandomString(allowedChars, random, stringlaenge);
		}
	}

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

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

		if (r > l)
		{
			v = a[r];
			i = l-1;
			j = r;
			for (;;)
			{
				while (a[++i].compareTo(v) < 0) ;
				while (j > 0 && a[--j].compareTo(v) > 0) ;
				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_rechts_Pivot(a, l, i-1);
			quicksort_rechts_Pivot(a, i+1, r);
		}
	}

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

		if (r > l)
		{

			t = a[l];
			a[l] = a[r];
			a[r] = t;

			v = a[r];
			i = l-1;
			j = r;
			for (;;)
			{
				while (a[++i].compareTo(v) < 0) ;
				while (j > 0 && a[--j].compareTo(v) > 0) ;
				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_Links_Pivot(a, l, i-1);
			quicksort_Links_Pivot(a, i+1, r);
		}
	}


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

		if (r > l)
		{
			String temp = a[((r+1)-l)/2];
			t = temp;
			temp = a[r];
			a[r] = temp;

			v = a[r];
			i = l-1;
			j = r;
			for (;;)
			{
				while (a[++i].compareTo(v) < 0) ;
				while (j > 0 && a[--j].compareTo(v) > 0) ;
				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_mitte(a, l, i-1);
			quicksort_mitte(a, i+1, r);
		}
	}

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

		if (r > l)
		{
			String temp = median(a[l], a[r], a[((r+1)-l)/2]);
			if(temp.equals(a[l]))
			{
				t = a[l];
				a[l] = a[r];
				a[r] = t;

			}

			if(temp.equals(a[((r+1)-l)/2]))
			{
				t = a[((r+1)-l)/2];
				a[((r+1)-l)/2] = a[r];
				a[r] = t;

			}

			v = a[r];
			i = l-1;
			j = r;
			for (;;)
			{
				while (a[++i].compareTo(v) < 0) ;
				while (j > 0 && a[--j].compareTo(v) > 0) ;
				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_rechtsLinksMitteMedian_Pivot(a, l, i-1);
			quicksort_rechtsLinksMitteMedian_Pivot(a, i+1, r);
		}
	}

	public static String median(String x, String y, String z)
	{
		return x.compareTo(y) < 0 ? y.compareTo(z) < 0 ? y : x.compareTo(z) < 0 ? z : x : y.compareTo(z) < 0 ? x.compareTo(z) < 0 ? x : z : y;
	}
}