开发者

Quick sort with vectors strange bugs

HI, I need help with this function im writing for hw. its not working even though it works fine with arrays instead of vectors. can anyone help please? Thanks in advance :].

void quick2 (vector <int> & qlist2, int left, int right) {
    int i = left, j = right;
    int middle =开发者_StackOverflow社区 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);
}


Try declaring your function as:

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

And omitting the return statement.

The problem is that arrays are passed by pointer in C and C++. Each recursive call receives a copy of a pointer to the same block of memory and modifies the same array, allowing the modifications to the array made by the recursive calls to be seen by the caller.

Vectors are objects, so each recursive call is passed a complete copy of the vector. Any modifications made by the recursive calls are not seen by the caller. The change above instead passes a reference to the vector so that it is not copied for each new function call. Instead, all the calls operate on the same object.

Also, check your initialization of middle. As written, you're taking the middle element of the array, which will be the same in each call. (Remember, qlist2.size() isn't going to change from call to call).

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜