Quicksort1

Ein Array (oder ein Teilbereich eines Arrays) wird durch Übergabe des unteren Start- und oberen Schlussindex in zwei Teilfelder aufgeteilt und der Wert des die Mitte markierenden Elementes gespeichert. Das erste Teilfeld wird von unten nach oben, das zweite von oben nach unten durchlaufen und es wird geprüft ob der Wert des jeweiligen Elementes kleiner bzw. größer als derjenige des mittleren Elementes ist. Ist dies nicht der Fall, werden die Elemente im Feld getauscht. Der Index des zweiten Teilfeldes wird dann als oberer Index an die rekursive Wiederholung des Ablaufs übergeben.

public class Quicksort {

    public static int[] intArr = { 16, 23, 14, 7, 21, 20, 6, 1, 17, 13, 12, 9, 3, 19 };

    public int[] sort(int l, int r) {
        int q;
        if (l < r) {
            q = partition(l, r);
            sort(l, q);
            sort(q + 1, r);
        }
        return intArr;
    }

    int partition(int l, int r) {

        int i, j, x = intArr[(l + r) / 2];
        i = l - 1;
        j = r + 1;
        while (true) {
            do {
                i++;
            } while (intArr[i] < x);

            do {
                j--;
            } while (intArr[j] > x);

            if (i < j) {
                int k = intArr[i];
                intArr[i] = intArr[j];
                intArr[j] = k;
            } else {
                return j;
            }
        }
    }

    public static void main(String[] args) {
        Quicksort qs = new Quicksort();
        int[] arr = qs.sort(0, intArr.length - 1);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(i + 1 + ": " + arr[i]);
        }
    }
}

1) Der hier gezeigt Algorithmus entstammt im Original der Seite http://www.sortieralgorithmen.de und wurde lediglich in Java transkribiert.