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

Question

Привет, мне нужна помощь с этой функцией, я пишу для 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 () не будет меняться от звонка к звонку).