Quicksort¹

public class Quicksort {

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

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

    private static 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) {
        int[] arr = sort(0, intArr.length - 1);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(i + 1 + ": " + arr[i]);
        }
    }
}

Vielen Dank an Kosmas Einbrodt, der mich auf einen Fehler aufmerksam machte: In der Method partition() fehlte in Zeile 19 die Endlosschleife, was bei größeren Arrays zu einem Stapelüberlauf führte.

Er verwies zudem auf die Schriften von Niklaus Wirth zu Algorithmen und Datenstrukturen, in deren Oberon-Ausgabe² ab Seite 64 ein eleganter Quicksort-Algorithmus vorgestellt wird, den Kosmas Einbrodt wie folgt nach Java transkribiert:

public static void quickSortWirth(int arr[], int l, int r) {
    int i, j, w, x;
    i = l;
    j = r;
    x = arr[(l + r) / 2];
    do {
        while (arr[i] < x)
            i++;
        while (x < arr[j])
            j--;
        if (i <= j) {
            w = arr[i];
            arr[i] = arr[j];
            arr[j] = w;
            i++;
            j--;
        }
    } while (i <= j);
    if (l < j)
        quickSortWirth(arr, l, j);
    if (i < r)
        quickSortWirth(arr, i, r);
}

Quellen

1. Der hier gezeigt Algorithmus entstammt im Original der Seite http://www.sortieralgorithmen.de und wurde lediglich in Java transkribiert.
2. Niklaus Wirth 1985 (Oberon version: August 2004), Algorithms and Data Structures https://people.inf.ethz.ch/wirth/AD.pdf

---