Неправильный вывод при запуске с этим кодом сортировки слиянием - PullRequest
Новая
       15

Неправильный вывод при запуске с этим кодом сортировки слиянием

0 голосов
/ 17 марта 2019

Я реализовал алгоритм сортировки слиянием.Я отладил код правильно.но не в состоянии определить, в чем проблема с моим кодом.Вот мой код: 

#include<iostream>
using namespace std;
void merge(int* l,int nL,int* r,int nR,int * a){
    //merging the arrays
    int i=0,j=0,k=0;
    while(i<nL && j<nR){
        if(l[i]<=r[j]){
            i++;
            a[k]=l[i];
        }

        else{
            j++;
            a[k]=r[j];
        }
        k++;
    }
    //now elements that are left out
    while(i<nL){
        a[k]=l[i];
        k++;
        i++;
    }
    while(j<nR){
        a[k]=r[j];
        j++;
        k++;
    }
}

Это моя mergeSort функция для реализации алгоритма сортировки слиянием. 

void mergeSort(int* a,int n){
    //base case
    if(n<2)
        return;
    //rec case
    int mid=n/2;
    //take 2 arrays of size mid & (n-mid)
    int nL=mid;
    int nR=n-mid;
    int l[nL];
    int r[nR];
    //fill the arrays
    for(int i=0;i<mid;i++){
        l[i]=a[i];
    }
    for(int i=mid;i<n;i++){
        r[i-mid]=a[i];
    }
    //call merge sort recursively
    mergeSort(l,nL);
    mergeSort(r,nR);
    merge(l,nL,r,nR,a);
}

Вот основная функция, гдеЯ принимаю массив в качестве входных данных и передаю функции mergeSort 

int main(){
    int a[100];
    cout<<"Enter no of elements"<<endl;
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    mergeSort(a,n);
    cout<<"After sorting with merge sort"<<endl;
    for(int i=0;i<n;i++){
        cout<<a[i]<<" ";
    }

    return 0;
}

Функция merge () объединяет два массива и mergeSort является функцией разделения массива и реализации сортировки слиянием.

Я даю это в качестве ввода: 

8
2 4 1 6 8 5 3 7

Вывод: 

6 1006565088 2096014825 6 2098806136 2096014825 93 8

1 Ответ

2 голосов
/ 17 марта 2019

Проблема связана с тем, что значение i и j увеличивается до того, как значение будет присвоено левому и правому массивам при объединении функций. Цикл while должен быть: 

while(i<nL && j<nR){
        if(l[i]<=r[j]){

            a[k]=l[i];
            i++;  //here was the mistake.
        }

        else{

            a[k]=r[j];
            j++;  // here was the mistake
        }
        k++;
    }
...