Слияние сортирует неожиданный вывод в c ++ - PullRequest
Новая
       10

Слияние сортирует неожиданный вывод в c ++

0 голосов
/ 26 апреля 2020

Это мой код для сортировки слиянием, но этот код выводит неправильный ответ, и я проверил несколько раз, но не смог выяснить причину неправильного вывода. Я был бы благодарен, если кто-нибудь может сказать мне, почему это происходит. 

#include<bits/stdc++.h>
    using namespace std;
    void merge(int a[],int l,int m,int h){
        int n1=m-l+1;
        int n2=h-m;
        int L[n1],R[n2];
        int i,j,k;
        for( i=0;i<n1;i++){
            L[i]=a[l+i];
        }
        for(j=0;j<n2;j++){
            R[j]=a[m+1+j];
        }
        i=0;j=0;k=0;
        while(i<n1 && j<n2){
            if(L[i]<R[j]){
                a[k]=L[i];
                i++;
            }else{
                a[k]=R[j];
                j++;
            }

            k++;
        }
        while(i<n1){
            a[k]=L[i];
            i++;
            k++;
        }
        while(j<n2){
            a[k]=R[j];
            k++;
            j++;
        }

    }
    void mergesort(int a[],int l,int h){
    if(l<h){
        int mid=l+(h-l)/2;
        mergesort(a,l,mid);
        mergesort(a,mid+1,h);
        merge(a,l,mid,h);
    }}
    void printArray(int A[], int size) 
    { 
        int i; 
        for (i=0; i < size; i++) 
            printf("%d ", A[i]); 
        printf("\n"); 
    } 
    int main(){
       int n;
        scanf("%d",&n);
        int arr[n];
        for(int i=0;i<n;i++){
            scanf("%d",&arr[i]);
        }
        int arr_size = sizeof(arr)/sizeof(arr[0]); 

        printf("Given array is \n"); 
        printArray(arr, arr_size); 

        mergesort(arr, 0, arr_size - 1);
        printf("\nSorted array is \n"); 
        printArray(arr, arr_size); 
        return 0; 

    }

Ввод:

5

5 4 3 2 1

Выход:

Заданный массив равен
5 4 3 2 1

Сортированный массив:
1 2 1 2 5

1 Ответ

1 голос
/ 26 апреля 2020

Вы инициализируете k с неправильным значением в merge.

k=0; будет держать указатель в начале, вместо этого используйте k=l;, чтобы начать копирование значений в текущий слева сегмент объединения переплет. 

void merge(int a[],int l,int m,int h){
    int n1=m-l+1;
    int n2=h-m;
    int L[n1],R[n2];
    int i,j,k;
    for( i=0;i<n1;i++){
        L[i]=a[l+i];
    }
    for(j=0;j<n2;j++){
        R[j]=a[m+1+j];
    }
    i=0;j=0;k=l;
    while(i<n1 && j<n2){
        if(L[i]<R[j]){
            a[k]=L[i];
            i++;
        }else{
            a[k]=R[j];
            j++;
        }

        k++;
    }
    while(i<n1){
        a[k]=L[i];
        i++;
        k++;
    }
    while(j<n2){
        a[k]=R[j];
        k++;
        j++;
    }
}
...