-4

これは、c ++で反転カウント用に作成したコードです。他の再帰メソッドを書く場合。私に説明してみてください。countI に反転カウントを格納しています。メイン関数で宣言した配列 A[] の出力として 2 を取得しています。

 #include<iostream>
 #include<math.h>


    using namespace std;
    int countI = 0;
    void merge(int A[], int p, int q, int r)
    {
        int n1 = q - p + 1;
        int n2 = r - q;
        int *L;
        L = new int[n1];
        int *R;
        R = new int[n2];
        for (int i = 1; i <= n1; i++)
        {
            L[i] = A[p + i - 1];
            //  cout << A[p + i - 1]<<endl;
            //cout << L[i];
        }
        for (int j = 1; j <= n2; j++)
            R[j] = A[q + j];
        int i = 1, j = 1;

        //  cout << "li " << L[n1]<<"\t"<<R[n2];

        for (int k = p; k <= r; k++)
        {

            if ((L[i] <= R[j] && i <= n1) || j>n2)
            {
                A[k] = L[i];
                //cout << A[k];
                i++;

            }
            else
            {
                A[k] = R[j];
                j++;
                if (i<n1)
                countI += n1 - i+1; //here I am counting the inversion.
                //cout <<endl<<"R"<< R[j];
            }
        }
    }
    void mergeSort(int A[], int p, int r)
    {
        if (p < r)
        {
            //      cout << A[8];
            int sum = p + r;
            //int q = (sum) / 2 + (sum % 2);
            int q = (sum) / 2;
            mergeSort(A, p, q);
            mergeSort(A, q + 1, r);
            merge(A, p, q, r);

        }
    }



    int main()
    {
        //I am considering array from index 1
        int A[] = { 0, 1, 3, 5,2,4,6 };
    //  int arr[100001];
        int i = 1;
        int n = 0;
        //while (scanf("%d", &n) != EOF) { arr[i++] = n; }

        mergeSort(A, 1, 6);
        for (int i = 1; i <= 6; i++)
        {
            cout << A[i] << " ";
        }
        cout << "\n " << countI;
        system("pause");
        return 0;
    }
4

1 に答える 1

1

C++ は 0 インデックス ベースの配列を使用することに注意してください。L と R の最初の要素は 1 ではなく 0 です。main で mergeSort を呼び出す場合も同じです。mergeSort(A, 0, 5) を試してください

1 から始まるインデックス付けの間違いと一貫性がありますが、配列の最後を 1 ずつ実行します。これにより、プログラムがクラッシュする可能性があります。ただし、そうでない場合は、メモリに不適切にアクセスして上書きしているため、奇妙な答え (デバッグが難しい) が得られることがよくあります。

以下は、マージソートの実行中に反転をカウントする (0 インデックスベースの配列の) 疑似コードです。

merge(A, p, m , q){
  B = [] // array size of q - p + 1
  i = p, j = m+1, k = 0, inv = 0
  while (i <= m && j <= q){
    if (A[i] < A[j])
      B[k++] = A[i++]
    else{
      B[k++] = A[j++]
      inv += m - i + 1
    }
  }
  while (i <= m)     // copy rest of left side to temp array
    B[k++] = A[i++]  // otherwise it may be overwritten
  i = 0;
  while (i < k){     // copy temp array elements back to A
    A[p+i] = B[i]
    ++i
  }
  return inv
}

merge_sort(A, p, q){
  if (p == q)
    return 0;
  m = floor((p + q)/2)
  inv1 = merge_sort(A, p, m)
  inv2 = merge_sort(A, m+1, q)
  return inv1 + inv2 + merge(A, p, m, q)
}

// you can call it like this:
A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}  // 10 Elements
inversions = merge_sort(A, 0, 9)    // sort and count inversions from index 0 to index 9
于 2015-07-09T15:39:44.837 に答える