マージソートの実装が期待通りに機能しない

Question

私はマージソートを実装しようとしています。実装は何とか間違っています - 出力には、元の配列の一部ではない値が含まれています。私はそれを他の人の実装（作業）と比較しようとしましたが、間違いを見つけることはできません。

コードは次のとおりです。 -

#include <iostream> 

using namespace std; 
void Merge (int A[], int lo, int hi, int mid){ 
    int i = lo; 
    int k = 0; 
    int j = mid+1; 
    int R[hi-lo]; 

    while(i<=mid && j<=hi){ 
     if(A[i]<A[j]){ 
      R[k]=A[i]; 
      cout << A[i] << "; " << A[j] << "  " << i << "  " << j << endl; 
      i++; 
     }else { 
      R[k]=A[j]; 
      cout << A[i] << "; " << A[j] << "  " << i << "  " << j << endl; 
      j++; 
     }k++; 
    } 
    while(i<=lo){ 
     R[k]=R[i]; 
     i++;k++; 
    } 
    while(j<=hi){ 
     R[k]=R[j]; 
     j++;k++; 
    } 
    int count =0; 
    for(i=lo; i<hi; i++){ 
     A[i]=R[count]; 
     count++; 
     cout << count << " ; " << i << "-/-/-/-/-/-/-" << flush; 
    } 
} 
void mergeSort(int A[], int lo, int hi){ 
    //if(hi-lo+1<2)return; 
    if (lo<hi){ 
    int mid = (lo+hi)/2; 
    mergeSort(A, lo, mid); 
    mergeSort(A, mid+1, hi); 
    Merge (A, lo, hi, mid);} 
} 

int main(){ 
    int A[] = {1,5,3,4,8,9,150,7,51,65}; 
    int hi = sizeof(A)/sizeof(int); 
    cout << hi << endl; 
    mergeSort(A,0, hi); 
    cout << endl << endl << endl << endl; 
    for(int i=0; i<=hi; i++){ 
     cout<<A[i]<< "; " << flush; 
    } 
    return 0; 
} 

私は似たQ（S）を検索しようとしましたが、ものを見つけることができませんでした。

Answer 1

実装の問題は、境界包含と誤った配列の混在です。マージのループは、あなたがやっている間

まず、最後の2を見て：あなたは、同じ機能でR[k]=A[i];

を意味R[k]=R[i];は、あなたのforループが反復が欠落している、ループガードはi<=hiの代わりi<hiする必要があります。

hiの初期化も間違っています。最後のインデックスではなく要素の数に初期化したので、-1を引いてください。

また、あなたのプリントコードが何をしているのかわからないので、私はコメントして自分自身を追加しました。

次のように私はあなたのコードを修正：

#include <iostream> 

using namespace std; 
void Merge (int A[], int lo, int hi, int mid){ 
    int i = lo; 
    int k = 0; 
    int j = mid+1; 
    int R[hi-lo]; 

    cout << "input" << endl; 
    for(int i=lo; i<=mid; i++) 
     cout << A[i] << " "; 
    cout << endl; 
    for(int i=mid+1; i<=hi; i++) 
     cout << A[i] << " "; 

    cout << endl; 

    while(i<=mid && j<=hi){ 
     if(A[i]<A[j]){ 
      R[k]=A[i]; 
      //cout << A[i] << "; " << A[j] << "  " << i << "  " << j << endl; 
      i++; 
     }else { 
      R[k]=A[j]; 
      //cout << A[i] << "; " << A[j] << "  " << i << "  " << j << endl; 
      j++; 
     }k++; 
    } 
    while(i<=mid){ 
     R[k]=A[i]; 
     i++;k++; 
    } 
    while(j<=hi){ 
     R[k]=A[j]; 
     j++;k++; 
    } 
    int count =0; 
    for(i=lo; i<=hi; i++){ 
     A[i]=R[count]; 
     count++; 
     //cout << count << " ; " << i << "-/-/-/-/-/-/-" << flush; 
    } 

    cout << "output:" << endl; 
    for(int i=lo; i<=hi; i++) 
     cout << A[i] << " "; 
    cout << endl; 
} 
void mergeSort(int A[], int lo, int hi){ 
    //if(hi-lo+1<2)return; 
    if (lo<hi){ 
    int mid = (lo+hi)/2; 
    mergeSort(A, lo, mid); 
    mergeSort(A, mid+1, hi); 
    Merge (A, lo, hi, mid);} 
} 

int main(){ 
    int A[] = {1,5,3,4,8,9,150,7,51,65}; 
    int hi = sizeof(A)/sizeof(int) -1; 
    cout << hi << endl; 
    mergeSort(A,0, hi); 
    cout << endl << endl << endl << endl; 
    for(int i=0; i<=hi; i++){ 
     cout<<A[i]<< "; " << flush; 
    } 
    return 0; 
}