package quicksort;

/**
 * @author Dominik JŠckle
 * @date 13.09.2008
 * @environment Eclipse
 * @description Implementierung des Quicksortalgorithmus
 * (Siehe Artikel "Quicksort" auf codehamster.wordpress.com)
 */

// Imports.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/*
 * Sortieralgorithmus Quicksort.
 */
public class Quicksort {
	
	private int a[];
	private int links = 0;
	private int rechts;

	private BufferedReader buf = new BufferedReader(new InputStreamReader(
			System.in));

	/*
	 * Konstruktor.
	 */
	public Quicksort() {
		a = Lese(a);
		System.out.println("Sie wollen folgende Liste sortieren");
		Ausgabe(a);

		rechts = a.length;
		Sort(links, rechts);

		System.out.println("Sortierte Liste:");
		Ausgabe(a);
	}

	/*
	 * Methode Lese() gibt Liste mit zu sortierenden Zahlen zurueck.
	 */
	private int[] Lese(int a2[]) {
		String help = "";
		String helparray[];

		System.out.println("Willkommen zum Zahlensortieren mittels Quicksort.");
		System.out
				.println("Bitte geben sie die zu sortierenden Zahlen ein: Zahl1,Zahl2,Zahl3...");

		try {
			help = buf.readLine();
		} catch (IOException e) {
			System.out.println(e.getMessage());
		}

		helparray = help.split(",");
		a2 = new int[helparray.length];

		for (int l = 0; l < helparray.length; l++) {
			a2[l] = Integer.valueOf(helparray[l]);
		}
		return a2;
	}

	/*
	 * Mehtode Ausgabe() gibt die Liste in der Konsole aus.
	 */
	public void Ausgabe(int a[]) {
		for (int k = 0; k < a.length - 1; k++) {
			System.out.print(a[k] + " | ");
		}
		System.out.print(a[a.length - 1]);
		System.out.println("");
	}

	/*
	 * Methode Sort() is der eigentliche Quicksortalgorithmus
	 */
	private void Sort(int links, int rechts) {
		int i, j;
		int pivot, h;

		if (links < rechts) {
			i = links;
			j = rechts - 1;
			pivot = a[(links + rechts) / 2];
			while (i <= j) {
				while (a[i] < pivot) {
					i++;
				}
				while (a[j] > pivot) {
					j--;
				}
				if (i <= j) {
					h = a[i];
					a[i] = a[j];
					a[j] = h;
					i++;
					j--;
				}
			}
			
			//j+1, da das Array von 0 loslaeuft, daher Indexprobleme
			if ((j - links) < (rechts - i)) {
				Sort(links, j+1);
				Sort(i, rechts);
			} else {
				Sort(i, rechts);
				Sort(links, j+1);
			}
		}
	}

	/*
	 * Mainmethode = Start des Programms
	 */
	public static void main(String[] args) {

		// neues Objekt der Klasse Quicksort instanzieren.
		new Quicksort();
	}
}