使用 C++ 程序的合并排序没有得到正确的输出

Question

我不知道这段代码有什么问题，但我花了太多时间来找出问题，但仍然无法解决问题，我认为复制数组有一些错误，因为其他一切似乎都是正确的

请检查此代码-

#include<iostream>
using namespace std;


void MergeArray(int arr[],int lb,int mid,int ub){
    int i=lb;
    int j=mid+1;
    int k=0;
    int newarr[ub-lb+1];

//condition required for comparison between the split parts
    while(i<=mid && j<=ub){
        if(arr[i] < arr[j]){
            newarr[k]=arr[i];
            k++;
            i++;
        }
//basically a[j]<a[i] in this else condition
        else{
            newarr[k]=arr[j];
            k++;
            j++;
        }
    }
//all th left out elements in a[i] when a[j] is finished are added to newarr
    while(i<=mid){
        newarr[k]=arr[i];
        k++;
        i++;
    }
//all th left out elements in a[j] when a[i] is finished are added to newarr
    while(j<=ub){
        newarr[k]=arr[j];
        k++;
        j++;
    }

//copying all the elements of newarr to original arr
//i think this part has something messed up
   for(int i=lb;i<=ub;i=i+1){
        arr[i]= newarr[i];
    }

}


void MergeElements(int arr[], int lb,int ub){
    int mid;
    if(lb<ub){
        mid=(lb+ub)/2;
        //spliting into 2 arts**
        MergeElements(arr,lb,mid);
        MergeElements(arr,mid+1,ub);
        //merging in sorted order**
        MergeArray(arr,lb,mid,ub);
    }

}

int main(){
    int n;
    cout<<"enter the size of the array"<<endl;
    cin>>n;
    int arr[n];
    cout<<"please enter the elements of the array"<<endl;
    for(int i=0;i<n;i++){
        cout<<"enter the element no."<<i<<endl;
        cin>>arr[i];
    }

    MergeElements(arr,0,n-1);

    cout<<"\tSorted Array Elements"<<endl;
    for(int i=0;i<n;i++){
        cout<<arr[i]<<"\t";
    }
return 0;
}

我想我无法正确获取数组，因为根据我的说法，其他一切似乎都是正确的，请检查

Answer 1

好吧，我将绕过您在 C++ 中使用可变长度数组 (VLA) 时遇到的问题（目前 - VLA 不是 Standard C++) 允许，首先，post 解决您的问题。这是（因为你在评论中正确 'guessed'）在这个循环中：

//i think this part has something messed up
   for(int i=lb;i<=ub;i=i+1){
        arr[i]= newarr[i];
    }

这里，虽然 i 索引（从给定的下限 lb 开始）对于 arr 数组是正确的，但不是 newarr 数组正确！这是在本地创建的，大小为 ub - lb + 1（正确），但索引 从零开始 - 因此您需要删除 [=20= 的 lb 偏移量]:

   for (i = lb; i <= ub; i++) { // NOTE: You've already declared "int i" - a new one will give a 'hides previous declaration' warning
        arr[i] = newarr[i - lb]; // *** You need to remove the lower-bound offset!
    }

关于C++中的VLA问题：我相信GCC/g++支持这些但是，如果你想遵守标准 C++ , 你应该使用 std::vector。所以，代替：

int newarr[ub - lb + 1];

使用：

std::vector<int> newarr(size_t(ub - lb + 1));

并在 main 函数中类似地使用 std::vector<int> arr(n);。对于代码的最小更改，您仍然可以保留 void MergeElements(int arr[], int lb, int ub) 签名但是，要使用 std::vector 调用它，您需要提供第一个元素的地址.所以，在 main 中使用这个：

MergeElements(&arr[0], 0, n - 1);

随时要求进一步澄清and/or解释。

Answer 2

写出将数组newarr复制到arr中的循环

//copying all the elements of newarr to original arr
//i think this part has something messed up
   for(int i=lb, k = 0;i<=ub; i++, k++){
        arr[i]= newarr[k];
    }

请注意可变长度数组不是标准的 C++ 功能。您可以使用标准容器 std::vector<int> 而不是可变长度数组 newarr。此外，使用标准算法可以使函数 MergeArray 的实现更加简单。给你

void MergeArray(int arr[],int lb,int mid,int ub){
    std::vector<int> newarr(ub-lb+1 );

    std::merge( arr + lb, arr + mid + 1, arr + mid + 1, arr + ub + 1, newarr.begin() );
    std::copy( newarr.begin(), newarr.end(), arr + lb );
}

Answer 3

这条评论下面的循环

// copying all the elements of newarr to original arr

对源和目标使用相同的索引——它不应该。要复制的 newarr[] 内容从索引 0 开始，而其在 arr[] 中的目标区域从索引 lb.

开始

使用 C++ 程序的合并排序没有得到正确的输出

Merge Sort using C++ Program not getting correct output

c++

arrays

sorting

mergesort

data-structures