Coder Wiki | Algorithmen

Quicksort ist ein schneller, rekursiver, nicht-stabiler Sortieralgorithmus, der nach dem Prinzip Teile und herrsche (engl. Divide and conquer) arbeitet.

Quicksort wählt ein Pivotelement ? aus der zu sortierenden Liste aus und zerlegt die Liste in zwei Teillisten, eine untere, die alle Elemente kleiner und eine obere, die alle Elemente gleich oder größer dem Pivotelement enthält. Diese Teillisten werden rekursiv sortiert.

Beispiel

[Get Code]

quicksort.java
void tausche(int daten[], int a, int b) {
        int temp = daten[a];
        daten[a] = daten[b];
        daten[b] = temp;
}
 
int teile(int daten[], int links, int rechts) {
        int index = links;
        for (int zeiger = links; zeiger < rechts; zeiger++) {
                if (daten[zeiger] <= daten[rechts]) {
                        tausche(daten, index, zeiger);
                        index++;
                }
        }
        tausche(daten, index, rechts);
        return index;
}
 
void quicksort(int daten[], int links, int rechts) {
        if (rechts > links) {
                int teiler = teile(daten, links, rechts);
                quicksort(daten, links, teiler - 1);
                quicksort(daten, teiler + 1, rechts);
        }
}