Tri rapide avec des vecteurs bogues étranges

Question

HI, j'ai besoin d'aide avec cette fonction im écrit pour hw. ça ne marche pas même si ça marche bien avec des tableaux au lieu de vecteurs. Quelqu'un peut-il aider s'il vous plaît? Merci d'avance :].

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

Essayez déclarant votre fonction:

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

Et en omettant la déclaration return.

Le problème est que les tableaux sont transmis par pointeur en C et C++. Chaque appel récursif reçoit une copie d'un pointeur vers le même bloc de mémoire et modifie le même tableau, ce qui permet aux modifications apportées au tableau par les appels récursifs d'être vues par l'appelant.

Les vecteurs sont des objets, donc chaque appel récursif est passé une copie complète du vecteur. Les modifications apportées par les appels récursifs ne sont pas visibles par l'appelant. La modification ci-dessus passe à la place une référence au vecteur afin qu'elle ne soit pas copiée pour chaque nouvel appel de fonction. Au lieu de cela, tous les appels fonctionnent sur le même objet.

Vérifiez également l'initialisation de middle. Comme écrit, vous prenez l'élément central du tableau, qui sera le même dans chaque appel. (Rappelez-vous, qlist2.size() ne va pas changer d'appel en appel).