マージソートマージン

Question

マージソートを実装しようとしています。私は、マージに問題があるが、私は入力9 8 7 6 5 4 3 2 1で

void mergeArays(vector<int> &a , int low , int mid , int high){ 
    int i = 0; 
    int j = mid + 1; 
    vector<int> final; 
    while(i != mid && j!= high){ 
     if(a[i] < a[j]){ 
      final.push_back(a[i++]); 
      continue; 
     } 
     final.push_back(a[j++]); 
    } 
    for(int i = 0; i < final.size() ;i++){ 
     a[i] = final[i]; 
    } 
} 

を宣言した

私はマージ機能に

void mergeSort(vector<int> &a , int low , int high){ 
    if(low < high){ 
     int mid = (low + high)/2; 
     mergeSort(a , low , mid); 
     mergeSort(a , mid + 1 , high); 
     mergeArays(a , low , mid , high); 
    } 
} 

を宣言している、それはcompetely間違った出力をスローします。マージの背後にある私の論理のバグやミスはどこにありますか？私はそれを見つけることができません、私はそれが良いはずですそれをcalcualteしようとするたびに。

おかげ

Answer 1

あなたがここにあなたのmergeArrays方法にバグがあります。ループを考えてみましょう：

while(i != mid && j!= high){ 
    if(a[i] < a[j]){ 
     final.push_back(a[i++]); 
     continue; 
    } 
    final.push_back(a[j++]); 
} 

ここで、2要素のサブアレイをマージしているとします。それらは以下のとおりです。

[3,9] // a[i] = 3, a[i+1] = 9 
[10,12] // j[i] = 10, j[i+1] = 12 

だからあなたのコードによると、i == midので、それは出力3と9になるだろう、と、ループが終了します。

すべてがコピーされることを確認するには、ループの後にクリーンアップする必要があります。正しいコードは次のようになります

while(i != mid && j!= high){ 
    if(a[i] < a[j]){ 
     final.push_back(a[i++]); 
     continue; 
    } 
    final.push_back(a[j++]); 
} 
while (i != mid) 
{ 
    final.push_back(a[i++]); 
} 
while (j != high) 
{ 
    final.push_back(a[j++]); 
} 

最初のループが終了するので、これら二つのクリーンアップループの一方のみが、入力されるノート、どちらかi == mid又はj == high。