import java.util.Random;

public class Giithub {

	public Giithub()
	{

	}

	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

		Giithub t = new Giithub();
		erzeugen(field, 50);
		kopieren(field, field1, field2, field3,field4);
		ausgeben(field);

		System.out.println();
		System.out.println("Bubblesort");
		Bubblesort(field);
		ausgeben(field);

		System.out.println();
		System.out.println("insertionsort");
		insertionsort(field1);
		ausgeben(field1);

		System.out.println();
		System.out.println("selectionsort");
		selectionsort(field2);
		ausgeben(field2);
		System.out.println();

		//		System.out.println();
		//		System.out.println("Quicksort");
		//		quicksort(0,arr.length-1,field3);
		//		ausgeben(field3);

		System.out.println("Quicksort");
		sort(field4,0,field4.length - 1);
//		QuicksortTextAusgeben();
		ausgeben(field4);

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

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

		System.out.println();
		System.out.println("Bubblesort");
		Bubblesort(arr);
		ausgeben(arr);

		System.out.println();
		System.out.println("insertionsort");
		insertionsort(arr1);
		ausgeben(arr1);

		System.out.println();
		System.out.println("selectionsort");
		selectionsort(arr2);
		ausgeben(arr2);

	}

	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 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 boolean getauscht;
	static public void Bubblesort(int[] feld)
	{
		int ver = 0;
		int t = 0;
		int j = feld.length-1;
		do
		{
			getauscht = false;
			for(int i = 0; i <= j-1; ++i)
			{
				if(feld[i] > feld[i+1])
				{
					swap(feld,i,i+1);
					t+=3;
					getauscht = true;
				}
				++ver;
			}
			j -= 1;
		}while(getauscht == true);
		System.out.println("Es wurde : " + t + " mal getauscht und");
		System.out.println("Es wurde : " + ver + " mal verglichen");
		System.out.println();
	}

	public static void swap(int[] feld1, int a, int b)
	{
		int temp = feld1[a];
		feld1[a] = feld1[b];
		feld1[b] = temp;
	}

	static public void insertionsort(int[] feld)
	{
		int ver = 0;
		int t = 0;
		for(int i = 1; i < feld.length;++i)
		{
			int temp = feld[i];
			t++;
			int j = i-1;
			while(j>=0 && feld[j] > temp)
			{
				feld[j+1] = feld[j];
				t++;
				--j;
			}
			ver++;
			feld[j+1] = temp;
			t++;
		}
		System.out.println("Es wurde : " + t + " mal getauscht und");
		System.out.println("Es wurde : " + ver + " mal verglichen");
		System.out.println();
	}

	static int verSelection = 0;
	public static void selectionsort(int[] feld)
	{
		int t  = 0;
		for(int i = 0; i < feld.length-1; ++i)
		{
			int min = minipos(feld,i);
			swap(feld,i,min);
			t += 3;
		}
		System.out.println("Es wurde : " + t + " mal getauscht und");
		System.out.println("Es wurde : " + verSelection + " mal verglichen");
		System.out.println();
	}

	public static int minipos(int[] feld,int ab)
	{
		int minIndex = ab;
		for (int i = ab+1; i<feld.length; i++)
		{
			if (feld[i]<feld[minIndex])
			{
				minIndex=i;
				verSelection++;
			}

		}
		return minIndex;
	}

	static int verglichenQuicksort = 0;
	static int getauschtQuicksort = 0;
	public static void quicksort(int l, int r, int[] arr)
	{
		int q;
		if(l < r)
		{
			verglichenQuicksort ++;
			q = partition(l,r,arr);
			quicksort(l,q,arr);
			quicksort(q+1,r,arr);

		}

	}

	public static int partition(int l,int r, int[]arr)
	{
		int i,j,x = arr[(l+r)/2];
		i = l-1;
		j = r+1;
		while(true)
		{
			do
			{
				i++;
				verglichenQuicksort ++;
			}while(arr[i]<x);

			do
			{
				j--;
				verglichenQuicksort ++;

			}while(arr[j]>x);

			if(i < j)
			{
				int k = arr[i];
				arr[i] = arr[j];
				arr[j] = k;
				getauschtQuicksort += 3;
				verglichenQuicksort ++;
			}
			else
			{
				return j;
			}
		}
	}

	static void sort(int[] array, int l, int r)
	{
		if (l < r) {
			// select pivot element (left-most)
			int pivot = array[l];
			// partition and shuffle around pivot
			int i = l;
			int j = r;
			while (i < j) {
				// move right to avoid pivot element
				i += 1;
				// scan right: find elements greater than pivot
				while (i <= r && array[i] < pivot) {
					i += 1;
				}
				// scan left: find elements smaller than pivot
				while (j >= l && array[j] > pivot) {
					j -= 1;
				}
				if (i <= r && i < j) {
					// swap around pivot
					swapq(array, i, j);
				}
			}
			// put pivot in correct place
			swapq(array, l, j);
			// sort partitions
			sort(array, l, j - 1);
			sort(array, j + 1, r);
		}
	}

	/**
	 * Swap elements at indexes {@code i} and {@code j}
	 * in the give array
	 *
	 * @param array
	 * @param i
	 * @param j
	 */
	static void swapq(int[] array, int i, int j)
	{
		if (i >= 0 && j >= 0 && i < array.length && j < array.length) {
			int tmp = array[i];
			array[i] = array[j];
			array[j] = tmp;
		}
	}


	static public void QuicksortTextAusgeben()
	{
		System.out.println("Es wurde : " + getauschtQuicksort + " mal getauscht und");
		System.out.println("Es wurde : " + verglichenQuicksort + " mal verglichen");
		System.out.println();
	}


	//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 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 ausgeben(String[] arr)
	{
		for(int i = 0; i < arr.length;++i)
		{
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}

	static boolean getauscht1;
	static public void Bubblesort(String[] arr)
	{
		int ver = 0;
		int op = 0;
		int j = arr.length-1;
		do
		{
			getauscht1 = false;
			for(int i = 0; i <= j-1; ++i)
			{
				if(arr[i].compareTo(arr[i+1]) > 0 )
				{
					swap(arr,i,i+1);
					op +=3;
					getauscht1 = true;
					ver++;
				}
			}
			j -= 1;
		}while(getauscht1 == true);
	}

	public static void swap(String[] arr, int a, int b)
	{
		String temp = arr[a];
		arr[a] = arr[b];
		arr[b] = temp;
	}

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

	static int opselSt =  0;
	static int verselSt = 0;
	public static void selectionsort(String[] arr)
	{
		for(int i = 0; i < arr.length-1; ++i)
		{
			int min = minipos(arr,i);
			{
				swap(arr,i,min);
				opselSt+= 3;
			}

		}
	}

	public static int minipos(String[] arr,int ab)
	{
		int minIndex = ab;
		opselSt ++;
		for (int i = ab+1; i<arr.length; i++)
		{
			if (arr[i].compareTo(arr[minIndex]) < 0)
			{
				minIndex=i;
				opselSt+=2;
			}
		}
		return minIndex;
	}
}