import java.util.Arrays;

/* ÜBUNGSSKRIPT-AUFGABEN 75 - */

public class Sortieralgorithmen {
	
	// Aufgabe 75
	public static void insertionSort(long[] numbers) {
		for (int i = 1; i < numbers.length; i++)
			for (int j = i-1; j >= 0; j--)
				if (numbers[j] > numbers[j+1])
					swap(numbers, j, j+1);
	}

	// Aufgabe 76
	public static void selectionSort(int[] array) {
		for (int i = 0; i < array.length-1; i++) {
			int maxIndex = i;
			for (int j = i+1; j < array.length; j++)
				if (array[j] > array[maxIndex])
					maxIndex = j;
			swap(array, i, maxIndex);
		}
	}
	
	// Aufgabe 77
	public static int bubbleSort(int[] arr) {
		int swapCounter = 0; // Zähler für return (Anzahl Vertauschungen)
		boolean finished = false; // wird true, wenn keine Vertauschung durchgeführt wurde
		int sortedElements = 0;  // Anzahl bereits einsortierter Elemente
		
		while (finished == false && sortedElements < arr.length) { // im letzten Schritt vertauschung durchgeführt und noch nicht alles einsortiert
			finished = true; // wir nehmen an, es würde im Folgenden keine Vertauschung geben (wird anderenfalls überschrieben)
			
			for (int i = 0; i < arr.length-sortedElements-1; i++) { // alle unsortierten Indizes (außer letzter wegen "i+1")
				if (arr[i] > arr[i+1]) {
					swap(arr, i, i+1); // -> vertauschen
					swapCounter++;
					finished = false; // hat eine Vertauschung gegeben
				}
			}
			
			sortedElements++;
		}
		
		return swapCounter;
	}
	
	// Aufgabe 78
	public static void mergeSort(int[] array) { 
		// (1.) Abbruchbedingung: nichts zu sortieren
		if (array.length <= 1) // kein/ein Element
			return;
		
		// (2.) Array in linke und rechte Hälfte teilen
		int sizeLeft = array.length / 2;
		int[] leftHalf = new int[sizeLeft];
		int[] rightHalf = new int[array.length - sizeLeft];
		for (int i = 0; i < sizeLeft; i++)
			leftHalf[i] = array[i];
		for (int i = 0; i < rightHalf.length; i++)
			rightHalf[i] = array[sizeLeft + i];
		
		// (3.) Beide Hälften sortieren
		mergeSort(leftHalf);
		mergeSort(rightHalf);
		
		// (4.) Die sortierten Hälften in das Ursprungsarray mergen
		int leftIndex = 0;
		int rightIndex = 0;
		int mergeIndex = 0;
		
		while (mergeIndex < array.length) {
			if (rightIndex >= rightHalf.length || leftIndex < leftHalf.length && leftHalf[leftIndex] < rightHalf[rightIndex]) {
				array[mergeIndex] = leftHalf[leftIndex];
				leftIndex++;
			} else {
				array[mergeIndex] = rightHalf[rightIndex];
				rightIndex++;
			}
			mergeIndex++;
		}
	}
	
	
	
	/* Vertauschen von Elementen (swap): */

	private static void swap(long[] numbers, int a, int b) {
		long tmp = numbers[a];
		numbers[a] = numbers[b];
		numbers[b] = tmp;
	}

	private static void swap(int[] numbers, int a, int b) {
		int tmp = numbers[a];
		numbers[a] = numbers[b];
		numbers[b] = tmp;
	}

	
	/* Test */
	
	public static void main(String[] args) {
		int[] a = new int[] {1,2,3,7,2312,2,4,6,2,4,9,7,3,2,3,42,1};
		mergeSort(a);
		System.out.println(Arrays.toString(a));
	}
}