Quicksort¹

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 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

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

Quicksort1

Quellen

Quicksort¹