dimanche 23 juin 2019

C++ recursive initialization of vectors using iterators produce inconsistent results

I was trying to practice C++ iterators by defining the very common mergesort algorithm when I encountered inconsistent program behavior. My question is NOT how to implement mergesort (which I both know and also realize has many example answers), but rather when creating recursive vectors using iterators that I receive inconsistent final results.

I'm aware that I could solve the issue by copying the values into L and R arrays through a for loop, but I would like to understand why using iterators is not working. This is running on CLION with C++ 14. This post Best way to extract a subvector from a vector? did not answer my question, as I'm creating vector similar to methods prescribed.

void merge2(vector<int> &arr, int l, int m, int r)
{
    vector<int> L{arr.begin()+l, arr.begin()+m+1};
    vector<int> R{arr.begin()+m+1,arr.begin()+r+1};
    int i = 0, j = 0, k = l;
    int n1 = m - l + 1;
    int n2 =  r - m;
    while (i < (n1) && j < (n2)){
        if (L[i]<=R[i]){
            arr[k] = L[i++];
        }
        else {
            arr[k] = R[j++];
        }
        k++;
    }
    while  (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }
    while(j < n2){
        arr[k] = R[j];
        j++;
        k++;
    }
}

/* l is for left index and r is right index of the
   sub-array of arr to be sorted */
void merge2Sort(vector<int> &arr, int l, int r)
{
    if (l < r)
    {
        // Same as (l+r)/2, but avoids overflow for
        // large l and h
        int m = l+(r-l)/2;
        // Sort first and second halves
        merge2Sort(arr, l, m);
        merge2Sort(arr, m+1, r);
        merge2(arr, l, m, r);
    }
}

int main(int argc, char **argv){
    vector<int> arr = {12, 11, 13, 5, 6, 7};
    merge2Sort(arr, 0, arr.size()-1);
    for(auto i = arr.begin(); i != arr.end(); i++){
        cout << *i << " ";
    }
    return 0;
}

Sometimes I receive the correct answer 5 6 7 11 12 13 and other times the incorrect answer 5 6 7 11 13 12. The answer should not vary by attempt.

Aucun commentaire:

Enregistrer un commentaire