Быстрая сортировка с векторами странные ошибки

Question

HI, мне нужна помощь с этой функцией im writing for hw. он не работает, даже если он отлично работает с массивами вместо векторов. может ли кто-нибудь помочь? Заранее спасибо :].

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

Попробуйте объявить вашу функцию:

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

И опуская return заявление.

Проблема в том, что массивы передаются указателем в C и C++. Каждый рекурсивный вызов получает копию указателя на один и тот же блок памяти и изменяет один и тот же массив, что позволяет модификациям массива, созданным рекурсивными вызовами, видимым вызывающим.

Векторы - это объекты, поэтому каждому рекурсивному вызову передается полная копия вектора. Любые изменения, вызванные рекурсивными вызовами, не отображаются вызывающим. Вместо этого изменение выше передает ссылку на вектор, чтобы он не копировался для каждого вызова новой функции. Вместо этого все вызовы работают на одном объекте.

Также проверьте свою инициализацию middle. Как написано, вы берете средний элемент массива, который будет одинаковым в каждом вызове. (Помните, что qlist2.size() не будет меняться от вызова к вызову).