import java.util.Arrays;  // für writeLineConsole(Arrays.toString(myArray));

public class QuickSort extends MiniJava {

	/** 1. Tausch von zwei Elementen [5m] */
	public static void swap(int[] numbers, int i, int j) {
		/*
		 * Dazu muss man (mindestens) eines der beiden zwischenspeichern, 
		 * da der Wert der ersten verloren geht sobald wir es mit dem 
		 * zweiten überschreiben.
		 */

		//writeLineConsole("Tausche " + numbers[i] + " und " + numbers[j]);  // Debug-Ausgabe
		int tmp = numbers[i];
		numbers[i] = numbers[j];
		numbers[j] = tmp;
	}
	
	/** 2. Partitionierung eines Array-Ausschnitts [30m] */
	public static int partition(int[] numbers, int left, int right) {		
		/*
		 * Das Pivot-Element steht ganz rechts, also müssen wir den Teil vor 
		 * dem Pivot-Element so sortieren, dass sich das Array in zwei
		 * Hälften unterteilen lässt. Aus [5 1 3 9 1 5 3] machen wir also
		 * zunächst einmal [1 1 _ _ _ _ 3], wobei "_" für die Elemente 
		 * größer/gleich des Pivot-Elements stehen (Reihenfolge egal).
		 * 
		 * Wir können zwei Indexzähler verwenden, wobei einer von rechts 
		 * (vor dem Pivot-Element) und einer von links beginnt. Den linken 
		 * Zähler erhöhen wir solange, bis wir auf ein Element stoßen, das 
		 * größer/gleich dem Pivot-Element ist. Den rechten Zähler erniedrigen 
		 * wir solange, bis wir auf ein Element stoßen, das kleiner ist als
		 * das Pivot-Element. Dann tauschen wir beide Elemente. Dieses 
		 * Vorgehen wiederholt sich solange, bis der linke Zähler
		 * größer/gleich dem rechten Zähler ist.
		 */
		
		int pivotIndex = right;
		
		while (left < right) {			
			while (left < right && numbers[left] < numbers[pivotIndex])
				left++;	
			
			while (left < right && numbers[right] >= numbers[pivotIndex])
				right--;		

			if (left != right)  // Tausch mit sich selbst wäre überflüssig
				swap(numbers, left, right);
			//writeLineConsole(Arrays.toString(numbers));  // Debug-Ausgabe		
		}
		
		/*
		 * Haben wir das geschafft, so müssen wir das Pivot-Element nur noch
		 * mit dem ersten "_"-Element tauschen, damit es richtig steht.
		 */
		
		swap(numbers, right, pivotIndex);  // right==left steht auf ersten "_"
		//writeLineConsole(Arrays.toString(numbers));  // Debug-Ausgabe
		return right;
	}
	
	/** 3. Rekursiver Quicksort-Algorithmus [15m] */
	public static void quicksort(int[] numbers, int left, int right) {
		/*
		 * Zunächst müssen wir das Array im übergegebenen Teilbereich
		 * (von left bis right) partitionieren. Das Pivot-Element ist
		 * anschließend richtig einsortiert und wir müssen den Teil
		 * vor dem (links vom) Pivot-Element und nach dem (rechts vom)
		 * Pivot-Element mittels Quicksort sortieren. Eine Partitionierung
		 * und Teilung in Teilbereiche ist nur nötig, wenn der Teilbereich
		 * eine Länge >= 2 hat.
		 */
		
		int length = right-left+1;
		
		if (length >= 2) {
			int middle = partition(numbers, left, right);
			quicksort(numbers, left, middle-1);
			quicksort(numbers, middle+1, right);
		}
	}
	
	/** 4. Hauptprogramm zum Testen mit einem zufälligen Array [10m] */
	public static void main(String[] args) {
		/*
		 * Wir ermitteln zunächst eine zufällige Anzahl an Elementen, 
		 * erzeugen dann ein Array von dieser Größe und befüllen es
		 * wiederum mit zufälligen Elemente. Anschließend lassen
		 * wir es mittels Quciksort sortieren. Die Grenzen sind der
		 * Index des ersten Elements (left) und der Index des letzten
		 * Elements (right).
		 * 
		 * Zufallszahl <x> zwischen 0 (inkl.) und n (exkl.):
		 * int x = (int) (n * Math.random());
		 * 
		 * Ausgabe eines Arrays <numbers> auf der Konsole:
		 * writeLineConsole(Arrays.toString(numbers));
		 */
		
		int laenge = (int) (20 * Math.random());
		int[] numbers = new int[laenge];
		
		for (int i = 0; i < laenge; i++) {
			numbers[i] = (int) (20 * Math.random());
		}
		
		//numbers = new int[] {2, 8, 7, 3, 0, 1, 5}; // Debugging (immer gleiches Array)
		
		writeLineConsole("Zufälliges Array:");
		writeLineConsole(Arrays.toString(numbers));
		
		quicksort(numbers, 0, numbers.length-1);

		writeLineConsole("Sortiertes Array:");
		writeLineConsole(Arrays.toString(numbers));
	}
	
}