Sort.java

package ch.hslu.exercises.sw14;


public class Sort {

    public static void insertionSort(final int[] a) {
        int elt;
        int j;
        Thread thread = new Thread();
        for (int i = 1; i < a.length; i++) {
            elt = a[i]; // next elt for insert
            j = i; // a[0]..a[j-1] already sorted
            while ((j > 0) && (a[j - 1] > elt)) {
                a[j] = a[j - 1]; // shift right
                j--; // go further left
            }
            a[j] = elt; // insert elt
        } // a[0]...a[j] sorted
    }

    public static void insertionSort2(final int[] a) {
        int elt;
        int j;
        for (int i = 2; i < a.length; i++) {
            elt = a[i]; // next elt for insert
            a[0] = elt; // dummy-element
            j = i; // a[1]..a[j-1] already sorted
            while (a[j - 1] > elt) {
                a[j] = a[j - 1]; // shift right
                j--; // go further left
            }
            a[j] = elt; // insert elt
        } // a[1]...a[j] sorted
    }

    public static void quickSort(final char[] a, final int left, final int right) {
        int up = left; // linke Grenze
        int down = right - 1; // rechte Grenze (ohne Trennelement)
        char t = a[right]; // rechtes Element als Trennelement
        boolean allChecked = false;
        do {
            while (a[up] < t) {
                up++; // suche grösseres (>=) Element von links an
            }
            while ((a[down] >= t) && (down > up)) {
                down--; // suche echt kleineres (<) Element von rechts an
            }
            if (down > up) { // solange keine Überschneidung
                exchange(a, up, down);
                up++;
                down--; // linke und rechte Grenze verschieben
            } else {
                allChecked = true; // Austauschen beendet
            }
        } while (!allChecked);
        exchange(a, up, right); // Trennelement an endgültige Position (a[up])
        if (left < (up - 1)) quickSort(a, left, (up - 1)); // linke Hälfte
        if ((up + 1) < right) quickSort(a, (up + 1), right); // rechte Hälfte, ohne T’Elt.
    }

    private static void exchange(final char[] a, final int firstIndex, final int secondIndex) {
        char tmp;
        tmp = a[firstIndex];
        a[firstIndex] = a[secondIndex];
        a[secondIndex] = tmp;
    }

    public static void selectionSort(final int[] a) {
        for (int i = 0; i < (a.length - 1); i++) {
            int index = i;
            for (int j = i + 1; j < a.length; j++) {
                if (a[j] < a[index]) {
                    index = j;
                }
            }
            int temp = a[i];
            a[i] = a[index];
            a[index] = temp;
        }
    }

    static void bubbleSort(int[] arr) {
        int temp = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 1; j < (arr.length - i); j++) {
                if (arr[j - 1] > arr[j]) {
                    //swap elements
                    temp = arr[j - 1];
                    arr[j - 1] = arr[j];
                    arr[j] = temp;
                }

            }
        }
    }

    private static char[] b;

    public static void mergeSort(final char[] a) {
        b = new char[a.length]; // zusätzlicher Speicher fürs Mergen
        mergeSort(a, 0, a.length - 1);
    }

    private static void mergeSort(final char a[], final int left, final int right) {
        int i, j, k, m;
        if (right > left) {
            m = (right + left) / 2; // Mitte ermitteln
            mergeSort(a, left, m); // linke Hälfte sortieren
            mergeSort(a, m + 1, right); // rechte Hälfte sortieren
            // "Mergen"
            for (i = left; i <= m; i++) { // linke Hälfte in Hilfsarray kopieren
                b[i] = a[i];
            }
            for (j = m; j < right; j++) { // rechte Hälfte umgekehrt in Hilfsa. kopieren
                b[right + m - j] = a[j + 1];
            }
            i = left;
            j = right; // Index für linke und rechte Hälfte
            for (k = left; k <= right; k++) { // füge sortiert in a ein
                if (b[i] <= b[j]) {
                    a[k] = b[i];
                    i++;
                } else {
                    a[k] = b[j];
                    j--;
                }
            }
        }
    }

}