2017-11-15 20 views
2

宿題のカウントインバージョンアルゴリズムを実装する必要がありますが、私のコードで何が問題であるか把握できませんでした。私は(唯一の私は<iostream>が含まれており、出力のみのためのSTDを使用することができます任意のC++ライブラリを使用せずに)ずっとそれでcout<<を動作しませんでした)、それはそれだ、また、彼はここに私たちにこの作品を与えた:C++でマージソートアルゴリズムを使用してカウント反転を実装する

void count_inversion(int a[],int n){ 
    count_inversion(a, n/2); 
    count_inversion(a + (n/2), n/2); 
    count_inversion_merge(a, n/2, n); 
    } 

を、私たちを言いましたcount_inversion_merge関数を実装し、この部分をヒントとして使用する必要があります。 私は少しコードを適応させようとしましたが、まだ運がありません。ここで

は私のコードです:

int count_inversion_merge(int array[], int mid, int n) { 
     for (k = 0; k < n; k++) { 
      if (j == n || (i < mid && array[i] < array[j])) { 
       b[k] = array[i]; 
       i++; 
      } else { 
       b[k] = array[j]; 
       j++; 
       inversion++; 
      } 
     } 

    } 

私の最初の入力int a[] ={ 2, 4, 1, 3, 5 };は3を返す必要がありますが、それは5 を返し、私の第二の出力は5であるべきと私は私がどこにあるか、誰かが指摘することができることを願っています。5.を取得しますエラー。

+3

デバッガとのラインで、あなたのコード行をステップ実行するとき、あなたは何を観察しましたか? – user0042

+0

私は配列のインデックスの値のために奇妙な出力を得て、毎回elseパートにジャンプします。 –

+1

小さな入力例では、手作業でアルゴリズムを実行できるはずです(そうでない場合は、問題を解決する前にアルゴリズムを理解しておく必要があります)。 – MrSmith42

答えて

3

あなたの基本的な考えは正しいですが、コードに2つの問題があります。一つは概念的、もう一つはコードです。マージステップの他のブロックで

  1. 、あなたは1で反転を増加しています。代わりに、左の部分にある値の数だけそれを増やす必要があります。したがってelseブロックではinversion++;の代わりにinversion += mid-i;を使用する必要があります。実際に必要なスワップの数を数える必要があるためです。この時点で、array[j]の値の場合、array[j]に対応するスワップに実際に必要とされた要素の数はmid - i(残りの配列の残りの部分)です。つまり、バブルソートを使用する場合は、左の配列(mid-i)のすべての残りの要素をこの単一の値(array[j])と入れ替える必要があります。したがって、このarray[j]の場合は、左のサブ配列の要素の数を増やす必要があります。

  2. count_inversionの再帰呼び出しでは、すべての呼び出しでいくつかの値が欠落しています。例えば例えばn=5と言うことができます。次に、左側に5/2 = 2、右側に5/2 = 2を使用しています。しかし、あなたは右の最後の要素を欠いています。 2番目の再帰呼び出しでは、次のようにして解決できます。ここでは、最初の呼び出しで使用した残りの長さを使用する必要があります。

    count_inversion(a + (n/2), n - n/2);

修正とあなたから少し変更したコード:https://ideone.com/raKD7T

+0

ありがとう@dipal私は2番目の点を完全に理解しています。私の場合、それは偶数の要素のために働くだろうが、要素数が奇数ならば、最後の要素は得られないだろうが、私は第1部分を理解していないので、答えを編集して解説を追加できますか?あなたの答えを右にマークしてください。 –

+1

私は説明しようとしましたが、より詳細な説明のために、@ H'Hのgeeksforgeeksのリンクを続けることができます。 http://www.geeksforgeeks.org/counting-inversions/ – dipal

+0

ご協力ありがとうございます –

関連する問題