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.
		 */

		// TO DO
	}
	
	/** 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.
		 */
		
		// TO DO
		
		/*
		 * Haben wir das geschafft, so müssen wir das Pivot-Element nur noch
		 * mit dem ersten "_"-Element tauschen, damit es richtig steht.
		 * Den neuen Pivot-Index geben wir zurück.
		 */
		
		// TO DO
	}
	
	/** 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.
		 */
		
		// TO DO
	}
	
	/** 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));
		 */
		
		// TO DO
	}
	
}