Quicksort verstehen

[Loddakwin]

Hallo Leute bin gerade dabei Quicksort zu verstehen jedoch macht mir dieser Teil zu schaffen. Ich weiß nicht in welcher Reihenfolge die Methoden in quicksort aufgerufen werden. Das Array ist danach sortiert also stimmt es wohl. Kann mir bitte wer erklären wie das funktioniert? Ich muss es verstehen!

public static void quicksort(Integer [] a,int p,int r){
        if(p<r){
            int q = partition(a,p,r); //In welcher Reihenfolge?
            quicksort(a,p,q-1); //In welcher Reihenfolge?
            quicksort(a,q+1,r); //In welcher Reihenfolge?
        }
    }
    public static int partition(Integer [] a,int p,int r){
        int x=a[r];
        int i=p-1;
        for(int j=p; j<r; j++){
            if(a[j].compareTo(x)<=0){
                i=i+1;
                swap(a,i,j);
            }}
           
            swap(a,i+1,r);
            
        return i+1;
       
    }

LG

 

[Robat]

Die Methoden werden in der Reihenfolge aufgerufen wie du sie hinschreibst.
Erst partition, dann quicksort mit q-1, dann quicksort mit q+1

Oder was genau verstehst du nicht ?

 

[Loddakwin]

Ja die Reihenfolge und ich weiß eben nicht wie ich mir das vorstellen kann. Die Rekursionen verwirren mich. Was passiert mit der letzten Zahl in quicksort q-1 ? Das array wird immer um 1 verringer danach wird wieder partition aufgerufen ? Was macht dann eigentlich der zweite quicksort aufruf noch?

 

[Robat]

Prinzipiell teilst du das Array immer in eine linke und eine rechte Hälfte und rufst mit diesen Teilarrays wieder den Quicksort-Algorithmus auf.
Erklärung dazu gibt es ja zuhauf im Netz.
Auf dieser Seite ist die Funktionsweise mEn schön grafisch aufbereitet und gut erklärt. Vielleicht hilft es dir ja.