私のC++マージソートプログラムで何が問題になっていますか？

Question

私はこの実装では窮地に追いついていません。サブアレイのマージ中に私のn2変数が上書きされていますが、これは何が原因でしょうか？ハードコーディングの値を試しましたが、うまくいかないようです。

#include <iostream> 
#include <cstdlib> 
#include <ctime> // For time(), time(0) returns the integer number of seconds from the  system clock 
#include <iomanip> 
#include <algorithm> 
#include <cmath>//added last nite 3/18/12 1:14am 

using namespace std; 

int size = 0; 

void Merge(int A[], int p, int q, int r) 
{ 
    int i, 
     j, 
     k, 
     n1 = q - p + 1, 
     n2 = r - q; 

    int L[5], R[5]; 

    for(i = 0; i < n1; i++) 
     L[i] = A[i]; 

    for(j = 0; j < n2; j++) 
     R[j] = A[q + j + 1]; 

    for(k = 0, i = 0, j = 0; i < n1 && j < n2; k++)//for(k = p,i = j = 1; k <= r; k++) 
    { 
     if(L[i] <= R[j])//if(L[i] <= R[j]) 
     { 
      A[k] = L[i++]; 
     } else { 
      A[k] = R[j++]; 
     } 
    } 
} 

void Merge_Sort(int A[], int p, int r) 
{ 
    if(p < r) 
    { 
     int q = 0; 
     q = (p + r)/2; 
     Merge_Sort(A, p, q); 
     Merge_Sort(A, q+1, r); 
     Merge(A, p, q, r); 
    } 
} 

void main() 
{ 
    int p = 1, 
     A[8]; 

    for (int i = 0;i < 8;i++) { 
     A[i] = rand(); 
    } 
    for(int l = 0;l < 8;l++) 
    { 
     cout<<A[l]<<" \n"; 
    } 
    cout<<"Enter the amount you wish to absorb from host array\n\n"; 
    cin>>size; 
    cout<<"\n"; 
    int r = size; //new addition 
    Merge_Sort(A, p, size - 1); 

    for(int kl = 0;kl < size;kl++) 
    { 
     cout<<A[kl]<<" \n"; 
    } 

} 

Answer 1

void Merge(int A[], int p, int q, int r) 
{ 
    int i, 
     j, 
     k, 
     n1 = q - p + 1, 
     n2 = r - q; 

    int L[5], R[5]; 

    for(i = 0; i < n1; i++) 
     L[i] = A[i]; 

あなただけL[5]を割り当てていますが、使用しているバインドn1を入力qとpに基づいている - と、発信者が書き込みできるようqとpの値を持つ関数を呼び出すために許可されています範囲外のL[]。これは他の自動変数を上書きするものとして現れることがありますが、未定義の動作であるため何かが起こる可能性があります。 （security vulnerabilitiesを含む）

これを解決するための最良の方法は何かわかりません - 固定長バッファーがなぜMerge()にあるのか分かりません。 - iが5以上の場合はL[i]にアクセスしないでください。

この全体の会話はR[]についても保持されます。 *AがMerge()に渡されているので、配列アクセスが常にバインドされていることを確認するのも理にかなっています。 （私はそれらが外れていることに気づいていませんが、このコードはとにかく再作業する必要があるので、私は慎重に探しているとは思わない）

Answer 2

プログラムをコンパイルするためにどのツールを使用していますか？この種のもののチェックをe、gに切り替えるフラグがいくつかあります。 gcc（例：-fmudflap、私はそれを使用していませんが、見た目は有用です）。

デバッガ（gdbなど）を使用できる場合は、変数n2に「データ監視」を追加する必要があります。デバッガはn2への書き込みを検出したときにプログラムを停止します。それはバグを追跡するのに役立ちます。またはvalgrindを試してください。

一時的にバグのこのタイプを停止するための簡単な技術はそう、ゴミ箱に移動ばかり1の周りにいくつかのダミー変数を置くことです：

int dummy1[100]; 
int n2 = r - q; 
int dummy2[100]; 

int L[5], R[5]; 

変数は通常、配列の境界を越えて書き込みコードによって引き起こされるゴミ箱に移動されています。 原因は最も近い可能性が高いので、R[5]と思われます。ダミーを見て、何が書かれているのかを知ることができ、何が起きているのかを推測することができます。

他のオプションは、問題を追跡しながら、すべてのアレイを大きくすることです。正しい範囲を超えて値を既知の値に設定し、変更しない値をチェックします。

これらの小切手を行うには小さなマクロを作成し、便利な場所にドロップできます。

Answer 3

先ほど同様のMerge関数を使用していましたが、正しく動作していないようです。その後、私はデザインを変更しましたが、今は完璧に動作します。以下は、C++のマージ関数の再設計された関数定義です。

void merge(int a[], int p, int q, int r){ 
    int n1 = q-p+1;    //no of elements in first half 
    int n2 = r-q;    //no of elements in second half 
    int i, j, k; 

    int * b = new int[n1+n2]; //temporary array to store merged elements 

    i = p; 
    j = q+1; 
    k = 0; 
    while(i<(p+n1) && j < (q+1+n2)){  //merging the two sorted arrays into one 
     if(a[i] <= a[j]){ 
      b[k++] = a[i++]; 
     } 
     else 
      b[k++] = a[j++]; 
    } 

    if(i >= (p+n1))   //checking first which sorted array is finished 
     while(k < (n1+n2))  //and then store the remaining element of other 
      b[k++] = a[j++]; //array at the end of merged array. 
    else 
     while(k < (n1+n2)) 
      b[k++] = a[i++]; 

    for(i = p,j=0;i<= r;){  //store the temporary merged array at appropriate 
     a[i++] = b[j++];  //location in main array. 
    } 

    delete [] b; 
} 

私はそれが役に立ちそうです。