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