Сортировка слиянием с использованием программы на 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

Хорошо, я собираюсь обойти проблему с использованием массива переменной длины (VLA) в C++ (на данный момент - VLA не разрешено в Стандарт C++) и, во-первых, опубликуйте решение вашей проблемы. Это (как вы правильно «догадались» в ваших комментариях) в этом l oop:

//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 (правильный), но индексы начинаются с нуля - поэтому вам необходимо удалить смещение lb для newarr:

   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!
    }

По вопросу VLA в C++: я считаю, GCC/g++ поддерживает их, но, если вы хотите соответствовать Стандарту C++, вы должны использовать std :: vector. Таким образом, вместо:

int newarr[ub - lb + 1];

используйте:

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

и аналогично используйте std::vector<int> arr(n); в вашей функции main. Для минимальных изменений в вашем коде вы все равно можете сохранить свою void MergeElements(int arr[], int lb, int ub) подпись, но, чтобы вызвать ее с помощью std::vector, вам нужно указать адрес первого элемента. Так, в main используйте это:

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

Не стесняйтесь просить дальнейших разъяснений и / или объяснений.

Answer 2

l oop под этим комментарием

// copying all the elements of newarr to original arr

использует один и тот же индекс для источника и назначения - и не должен. Копируемое содержимое newarr[] начинается с индекса 0, а область назначения в arr[] начинается с индекса lb.

Answer 3

Запишите l oop, который копирует массив 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 ++. Вместо массива переменной длины newarr вы можете использовать стандартный контейнер std::vector<int>. Кроме того, использование стандартных алгоритмов упрощает реализацию functionMergeArray. Вот вы

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 );
}