C++ Quicksort Rekusiv



  • Hi Leute,
    könnt ihr mir sagen was ich falsch gemacht habe?
    Quicksort Itterativ implementieren habe ich hinbekommen, Rekusiv will nicht ganz

    int Partition(vector <int>& A, int p , int r){
        int pivot = A[r];
        int i = (p-1);
    
        for(int j = p; j<(r-1); ++j){
            if(A[j] < pivot){
                swapA(A,j,++i);
            }
        }
        swapA(A,r,++i);
        return i;
    }
    
    void quickSort(vector<int>& A, int p, int r){
        if(p < r){
            int q = Partition(A,p,r);
            quickSort(A,p,(q-1));
            quickSort(A,(q+1),r);
        }
    }
    

    Habe die Funktion mit
    vector<int> A;
    A.push_back(10);
    A.push_back(15);
    A.push_back(5);
    A.push_back(1);
    A.push_back(0);
    A.push_back(2);
    quickSort(A,0,A.size()-1);
    Aufgerufen

    Der Vector sieht am dann wie folgt aus:
    1
    2
    10
    5
    15
    0

    Könntet ihr mir sagen wo ich falsch abgebogen bin?

    // EDIT swapA(A,r,++i) würde A[r] mit A[++i] swappen



  • Was hast du überprüft?



  • manni66 schrieb:

    Was hast du überprüft?

    manni66 schrieb:

    Was hast du überprüft?

    ich habe mir nach dem "sortieren" das array ausgeben lassen, mehr nicht
    (unter halb meines codes meine eingabe/ausgabe)



  • Ich würde vorschlagen: schau dir doch mal in jedem Rekursionsschritt dein Pivot Element, die Grenzen, und den resultierenden Vektor an.

    Vielleicht zusammen mit der Frage, was erwartest du, wie deine Partition danach aussehen soll?



  • Dann fang mal an zu debuggen.
    Liefert Partition ein richtig partitioniertes Array?
    Ist das gelieferte q plausibel?
    Was passiert in den Rekursionsschritten?

    Benutze Debugausgaben und/oder einen Debugger.



  • fehler liegt in zeile 5
    <= nicht nur <
    habe ich leider so aus dem script übernommen


Anmelden zum Antworten