public class Sort {

  /*
   * Hilfsmethode: Initialisierung eines Feldes mit Zufallszahlen
   */
    static int[] initArray (int num) {
	int[] result = new int[num];
	for (int i = 0; i < num; i++)
	    result[i] = (int) (Math.random () * 100.0);
	return result;
    }
    
  /*
   * Hilfsmethode: Ausgabe der Elemente eines Feldes
   */
    static void printArray (int[] array) {
	for (int i = 0; i < array.length; i++)
	    System.out.print (array[i] + " ");
	System.out.println ();
    }
    
    /*
     * Hilfsmethode: Austauch zweier Feldelemente
     */
    static void swap (int[] array, int idx1, int idx2) {
	int tmp = array[idx1];
	array[idx1] = array[idx2];
	array[idx2] = tmp;
    }
    
    static void insertionSort (int[] array) {
	for (int i = 1; i < array.length; i++) {
	    int marker = i;
	    int temp = array[i];
	    // f�r alle Elemente links vom Marker-Feld
	    while (marker > 0 && array[marker - 1] > temp) {
		// verschiebe alle gr��eren Element nach hinten
		array[marker] = array[marker - 1];
		marker--;
	    }
	    // setze temp auf das freie Feld 
	    array[marker] = temp;
	}
    }

  /*
   * Implementierung des SelectionSort
   */
    static void selectionSort (int[] array) {
	int marker = array.length - 1;
	while (marker >= 0) {
	    // bestimme gr��tes Element
	    int max = 0;
	    for (int i = 1; i <= marker; i++)
		if (array[i] > array[max])
		    max = i;
	    
	    // tausche array[marker] mit diesem Element
	    swap (array, marker, max);
	    marker--;
	}
    }
    
    /*
     * Implementierung des Bubble-Sort
     */
    static void bubbleSort1 (int[] array) {
	boolean swapped;
	
	do {
	    swapped = false;
	    
	    for (int i = 0; i < array.length - 1; i++) {
		if (array[i] > array[i + 1]) {
		    // Elemente vertauschen
		    swap (array, i, i + 1);
		    swapped = true;
		}
	    }
	    // solange Vertauschung auftritt
	} while (swapped);
    }
    
  /*
   * Verbesserte Implementierung des Bubble-Sort
   */
    static void bubbleSort2 (int[] array) {
	boolean swapped; // Vertauschung ?
	int max = array.length - 1; // obere Feldgrenze
	do {
	    swapped = false;
	    
	    for (int i = 0; i < max; i++) {
		if (array[i] > array[i + 1]) {
		    // Elemente vertauschen
		    swap (array, i, i + 1);
		    swapped = true;
		}
	    }
	    max--;
	    // solange Vertauschung auftritt
	} while (swapped);
    }
    
    /*
     * Implementierung des MergeSort
     */
    
    // Hilfsmethode f�r rekursives Sortieren durch Mischen
    static void msort (int[] array, int l, int r) {
	int i, j, k;
	int[] b = new int[array.length];
	
	if (r > l) {
	    // zu sortierendes Feld teilen
	    int mid = (r + l) / 2;
	    // Teilfelder sortieren
	    msort (array, l, mid);
	    msort (array, mid + 1, r);
	    
	    // Ergebnisse mischen �ber Hilfsfeld b
	    for (i = mid + 1; i > l; i--)
		b[i - 1] = array[i - 1];
	    for (j = mid; j < r; j++)
		b[r + mid - j] = array[j + 1];
	    for (k = l; k <= r; k++)
		if (b[i] < b[j])
		    array[k] = b[i++];
		else
		    array[k] = b[j--];
	    
	}
    }
    
    static void mergeSort (int[] array) {
	msort (array, 0, array.length - 1);
    }
    
    /*
     * Implementierung des QuickSort
     */
    
    // Hilfsmethode f�r rekursives Sortieren
    static void qsort (int[] array, int l, int r) {
	int lo = l, hi = r;

	if (hi > lo) {
	    // Pivotelement bestimmen
	    int mid = array[(lo + hi) / 2];
	    while (lo <= hi) {
		// Erstes Element suchen, das gr��er oder gleich dem
		// Pivotelement ist, beginnend vom linken Index
		while ((lo < r) && (array[lo] < mid))
		    ++lo;
		
		// Element suchen, das kleiner oder gleich dem
		// Pivotelement ist, beginnend vom rechten Index
		while (( hi > l ) && ( array[hi] > mid))
		    --hi;
		
		// Wenn Indexe nicht gekreuzt --> Inhalte vertauschen
		if (lo <= hi) {
		    swap(array, lo, hi);
		    ++lo;
		    --hi;
		}
	    }
	    // Linke Partition sortieren
	    if (l < hi) {
		qsort (array, l, hi);
	    }
	    
	    // Rechte Partition sortieren
	    if (lo < r) {
		qsort( array, lo, r);
	    }
	}
    }
    
    static void quickSort (int[] array) {
	qsort (array, 0, array.length - 1);
    }
    
    public static void main(String[] args) {
	int[] array = null;
	array = initArray (20);
	mergeSort (array);
	printArray (array);

	array = initArray (20);
	quickSort (array);
	printArray (array);

	array = initArray (20);
	selectionSort (array);
	printArray (array);

	array = initArray (20);
	insertionSort (array);
	printArray (array);

	array = initArray (20);
	bubbleSort2 (array);
	printArray (array);
	
	array = initArray (20);
	quickSort (array);
	printArray (array);

    }
}