jeudi 31 mai 2018

Passing vector by reference makes iterative algorithm run differently

This one has me baffled. I was implementing the Dutch national flag problem in C++. I forgot to pass my array by reference initially, but was displaying the array at every step, which helped me conclude that my algorithm worked fine. To fix the minute error of the vector not getting partitioned finally, I changed the function definition to pass vector as reference, which somehow produced an error.

I have never encountered something like this before. The code isn't recursive, and so while the function is running it shouldn't matter whether it is running on a copy of the vector or is running on the actual vector.

Here is the code:

#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>

using namespace std;

void optArr(vector<int> arr){
    for(auto i: arr){
        cout<<setw(3)<<i<<" ";
    }
    cout<<endl;
}

void _partition(vector<int> arr, int lo, int hi, int &i, int &k){  //Vector passed by value
    i=lo-1, k=hi+1;
    int ptr=lo, pivot=arr[hi];
    while(ptr<k){
        optArr(arr);
        cout<<"i: "<<i<<" ptr: "<<ptr<<" k: "<<k<<endl;
        if(arr[ptr]<pivot){
            swap(arr[++i],arr[ptr++]);
        }else if(arr[ptr] == arr[pivot]){
            ptr++;
        }else{
            swap(arr[--k],arr[ptr]);
        }
    }
}



int main(){
    vector<int> arr = {57,22,85,17,11,04,17,93,1,17,25,17};
    int i,k;
    _partition(arr, 0, arr.size()-1, i, k);
    optArr(arr);
    cout<<"i: "<<i<<" ptr: "<<0<<" k: "<<k<<endl;

    return 0;
}

And the output when vector is passed by value:

 57  22  85  17  11   4  17  93   1  17  25  17
i: -1 ptr: 0 k: 12
 17  22  85  17  11   4  17  93   1  17  25  57
i: -1 ptr: 0 k: 11
 17  22  85  17  11   4  17  93   1  17  25  57
i: -1 ptr: 1 k: 11
 17  25  85  17  11   4  17  93   1  17  22  57
i: -1 ptr: 1 k: 10
 17  17  85  17  11   4  17  93   1  25  22  57
i: -1 ptr: 1 k: 9
 17  17  85  17  11   4  17  93   1  25  22  57
i: -1 ptr: 2 k: 9
 17  17   1  17  11   4  17  93  85  25  22  57
i: -1 ptr: 2 k: 8
  1  17  17  17  11   4  17  93  85  25  22  57
i: 0 ptr: 3 k: 8
  1  17  17  17  11   4  17  93  85  25  22  57
i: 0 ptr: 4 k: 8
  1  11  17  17  17   4  17  93  85  25  22  57
i: 1 ptr: 5 k: 8
  1  11   4  17  17  17  17  93  85  25  22  57
i: 2 ptr: 6 k: 8
  1  11   4  17  17  17  17  93  85  25  22  57
i: 2 ptr: 7 k: 8
 57  22  85  17  11   4  17  93   1  17  25  17
i: 2 ptr: 0 k: 7

You can see that the output is correct, right up to the last one, which is called through the main function. When I saw this, I decided to pass the vector by reference by modifying the _partition signature to: void _partition(vector<int> &arr, int lo, int hi, int &i, int &k)

This produced the following output:

 57  22  85  17  11   4  17  93   1  17  25  17
i: -1 ptr: 0 k: 12
 17  22  85  17  11   4  17  93   1  17  25  57
i: -1 ptr: 0 k: 11
 25  22  85  17  11   4  17  93   1  17  17  57
i: -1 ptr: 0 k: 10
 17  22  85  17  11   4  17  93   1  25  17  57
i: -1 ptr: 0 k: 9
  1  22  85  17  11   4  17  93  17  25  17  57
i: -1 ptr: 0 k: 8
  1  22  85  17  11   4  17  93  17  25  17  57
i: 0 ptr: 1 k: 8
  1  93  85  17  11   4  17  22  17  25  17  57
i: 0 ptr: 1 k: 7
  1  17  85  17  11   4  93  22  17  25  17  57
i: 0 ptr: 1 k: 6
  1   4  85  17  11  17  93  22  17  25  17  57
i: 0 ptr: 1 k: 5
  1   4  85  17  11  17  93  22  17  25  17  57
i: 1 ptr: 2 k: 5
  1   4  11  17  85  17  93  22  17  25  17  57
i: 1 ptr: 2 k: 4
  1   4  11  17  85  17  93  22  17  25  17  57
i: 2 ptr: 3 k: 4
  1   4  11  17  85  17  93  22  17  25  17  57
i: 2 ptr: 0 k: 3

As you can see, this behaves abnormally right from the third line of output. I apologize for such a vague question, but I have no idea how else to go about looking for a solution to such an unusual problem.

Aucun commentaire:

Enregistrer un commentaire