Schnelle Sortierung mit Vektoren seltsame Bugs

Question

HI, ich brauche Hilfe mit dieser Funktion im Schreiben für hw. Es funktioniert nicht, obwohl es mit Arrays anstelle von Vektoren funktioniert. Kann mir bitte jemand helfen? Danke im Voraus :].

void quick2 (vector <int> & qlist2, int left, int right) { 
    int i = left, j = right; 
    int middle = qlist2[qlist2.size()/2]; 
    if (j - i < 1) { 
     return; 
    } 
    while (i <= j) { 
     while (qlist2[i] < middle) { 
      i++; 
     } 
     while (qlist2[j] > middle) { 
      j--; 
     } 
     if (i <= j) { 
      swap (qlist2[i], qlist2[j]); 
      i++; 
      j--; 
     } 
    } 

    if (left < j) 
     quick2 (qlist2, left, j); 
    if (i < right) 
     quick2 (qlist2, i, right); 
} 

Answer 1

Versuchen Sie, Ihre Funktion als deklarieren:

void quick2(vector<int> & qlist2, int left, int right) 

Und das Weglassen der return Aussage.

Das Problem besteht darin, dass Arrays von Zeiger in C und C++ übergeben werden. Jeder rekursive Aufruf empfängt eine Kopie eines Zeigers auf den gleichen Speicherblock und modifiziert das gleiche Array, wodurch die Änderungen an dem durch die rekursiven Aufrufe vorgenommenen Array vom Aufrufer gesehen werden können.

Vektoren sind Objekte, so dass jedem rekursiven Aufruf eine vollständige Kopie des Vektors übergeben wird. Alle durch die rekursiven Aufrufe vorgenommenen Änderungen werden vom Aufrufer nicht gesehen. Die obige Änderung übergibt stattdessen eine Referenz an den Vektor, so dass es nicht für jeden neuen Funktionsaufruf kopiert wird. Stattdessen werden alle Aufrufe für dasselbe Objekt ausgeführt.

Überprüfen Sie auch Ihre Initialisierung von middle. Wie geschrieben, nehmen Sie das mittlere Element des Arrays, das bei jedem Anruf gleich ist. (Denken Sie daran, qlist2.size() wird nicht von Call zu Call wechseln).