Сортировка слияния не работает полностью

Question

Код, который я сделал для сортировки слияния, приведен ниже. Дело в том, что при подаче ввода выходной сигнал . Что происходит не так?

#include <iostream> 
#include <cmath> 
using namespace std; 

int d[100]; 

void merge(int a[], int b[], int c[], int n) 
{ 
int n2=floor(n/2); 
int i=0, j=0, k=0; 
while(i<n2 && j<(n-n2)) 
{ 
    if(b[i]<c[j]) 
    { 
     d[k++]=b[i++]; 
    } 
    else if(b[i]>c[j]) 
    { 
     d[k++]=c[j++]; 
    } 
} 
    if(i==n2) 
    { 
     if(j<(n-n2)) 
     { 
      d[k++]=c[j++]; 
     } 
    } 
    if(i<n2) 
    { 
     d[k++]=b[i++]; 
    } 
} 


void mergesort(int a[], int n) 
{ 
int n2=floor(n/2); 
int b[50],c[50]; 
int i,j=0,k=0; 
for(i=0;i<n2;i++) 
{ 
    b[i]=a[k++]; 
} 
while(k<n) 
{ 
    c[j++]=a[k++]; 
} 
merge(a,b,c,n); 
} 

int main() 
{ 
int a[]={5,4,3,2,1}; 
int n=5; 
mergesort(a,n); 
for(int i=0;i<n;i++) 
{ 
    cout<<d[i]<<endl; 
} 
} 

Answer 1

Основная проблема заключается в том, что массивы (b и c), переданные для объединения, не сортируются. Другие проблемы заключаются в том, что алгоритм не является рекурсивным и что объединение не всегда ставит все числа из b и c в a.

версия, которая, кажется, работает с минимальными изменениями кода будет

void merge(int a[], int b[], int c[], int n) 
{ 
    int n2=floor(n/2); 
    int i=0, j=0, k=0; 
    while(k<n) 
    { 
    if((j == (n-n2) || b[i]<c[j]) && i < n2) 
    { 
     a[k++]=b[i++]; 
    } 
    else 
    { 
     a[k++]=c[j++]; 
    } 
    } 
} 


void mergesort(int a[], int n) 
{ 
    int n2=floor(n/2); 
    int b[50],c[50]; 
    int i,j=0,k=0; 
    for(i=0;i<n2;i++) 
    { 
    b[i]=a[k++]; 
    } 
    while(k<n) 
    { 
    c[j++]=a[k++]; 
    } 
    if(n2 > 1) { 
    mergesort(b, n2); 
    } 
    if(n - n2 > 1) { 
    mergesort(c, n - n2); 
    } 
    merge(a,b,c,n); 
} 

int main() 
{ 
    int a[]={5,4,3,2,1}; 
    int n=5; 
    mergesort(a,n); 
    for(int i=0;i<n;i++) 
    { 
    cout<<a[i]<<endl; 
    } 
} 

Answer 2

Вход для объединения должны быть отсортированы массивы, так как Филипп упоминалось ранее. Mergesort является рекурсивным. Для этого вам нужно разделить их, пока не достигнете точки, в которой у вас есть только один элемент массива (поэтому он отсортирован) и объединить все массивы, чтобы стать отсортированным результатом для ввода. Википедия - ваш друг, чтобы понять алгоритм: Mergesort

КТВ: Вам необходимо убедиться, что один из обоих случаев при сравнении в слиянии также проверяет равенство значений.

Answer 3

Обычно принято рекурсивно вызывать merge_sort, чтобы сортировать каждый поддиапазон до тех пор, пока поддиапазон не будет достаточно длинным, а затем объедините их вместе.

В вашем mergesort, b принимает 2 значения первого п/о a, то есть 5 и 4. c принимает остальные значения 3,2,1.

Вы тогда звоните merge (КСТАТИ Почему вы передаете a[] на это? Он не используется) Первый цикл

while(i<n2 && j<(n-n2)) 

будет n2 = 2 и n-n2 = 5-2 = 3 Это ставит 3 в начале, так и b[0]>c[0]=3 2 следующий с b[1]>c[1]=2 и 1 по d[2] по тем же причинам. Поскольку вы не рекурсируете, вы их не сортируете. Затем вы заканчиваете цикл while с i = 0, который меньше n2. Вы просто говорите

if(i<n2) 

так что вы просто скопировать первое из Ь, 5.

Все это дает 3, 2, 1, 5 и 0, потому что вы сделали d глобальным.

Answer 4

Филипп прав, нет рекурсивный в вашем коде вообще.

Однако есть еще некоторые ошибки. Я отметил его аннотациями, как и постскриптум Филиппа.

#include <iostream> 
#include <cmath> 
using namespace std; 

int d[100]; 

void merge(int a[], int b[], int c[], int n) 
{ 
    int n2=floor(n/2); 
    int i=0, j=0, k=0; 
    while(i<n2 && j<(n-n2)) 
    { 
     if(b[i]<c[j]) 
     { 
      d[k++]=b[i++]; 
     } 
     else if(b[i]>c[j]) 
     { 
      d[k++]=c[j++]; 
     } 
     /***************************************************/ 
     /* What if b[i] == c[j] here?      */ 
     /* Your code will drop into an infinity loop.  */ 
     /***************************************************/ 
    } 
    if(i==n2) 
    { 
     if(j<(n-n2)) 
     /****************************************************/ 
     /* Use **while** here?        */ 
     /* Because there may be more than one elements left */ 
     /* in c[].           */ 
     /****************************************************/ 
     { 
      d[k++]=c[j++]; 
     } 
    } 
    if(i<n2) 
    /***************************************************/ 
    /* Use **while** here? - With the same reason  */ 
    /***************************************************/ 
    { 
     d[k++]=b[i++]; 
    } 
} 


void mergesort(int a[], int n) 
{ 
    int n2=floor(n/2); 
    int b[50],c[50]; 
    int i,j=0,k=0; 
    for(i=0;i<n2;i++) 
    { 
     b[i]=a[k++]; 
    } 
    while(k<n) 
    { 
     c[j++]=a[k++]; 
    } 
    merge(a,b,c,n); 
} 

int main() 
{ 
    int a[]={5,4,3,2,1}; 
    int n=5; 
    mergesort(a,n); 
    for(int i=0;i<n;i++) 
    { 
     cout<<d[i]<<endl; 
    } 
} 

Answer 5

template <typename T> 
void merge(T arr[], int begin, int mid, int end) 
{ 
    int len = end - begin; 
    T *temp = new T[len]; 
    int i = begin; 
    int j = mid + 1; 
    int k = 0; 
    while (i <= mid && j <= end) 
    { 
     if(arr[i] <= arr[j]) 
      temp[k++] = arr[i++]; 
     else 
      temp[k++] = arr[j++]; 
    } 
    while (i <= mid) 
     temp[k++] = arr[i++]; 
    while(j <= end) 
     temp[k++] = arr[j++]; 

    memcpy(arr + begin, temp, len*sizeof(T)); 
    delete []temp; 
} 
template <typename T> 
void mergeSort(T arr[], int begin, int end) 
{ 
    if (begin >= end) 
     return; 

    int mid = (end + begin)/2; 
    mergeSort(arr, begin, mid); 
    mergeSort(arr, mid + 1, end); 
    merge(arr, begin, mid, end); 
}