0

マージソートを使用して配列の反転をカウントするプログラムを実装しました。プログラムはマージソートと同じですが、反転カウントがわずかに異なります。

public class HMergeSortVer1 {

    public int inversions;

    public void msort(int [] A,int p, int r){
        if(p<r){
            int q=(int) Math.floor((r+p)/2);
        //  System.out.println("q--"+q);
            msort(A, p, q);
            msort(A, q+1, r);
            merge(A,p,q,r);
        }

    }

    private void merge(int [] A,int p,int q,int r){
        //System.out.println("In the merge");
        int n1=q-p+1; // number of elements in left array
        int n2=(r-q);
        int[] L=new int[n1+1];
        int[] R=new int[n2+1];
        for(int i=0;i<n1;i++){
            L[i]=A[p+i];
        }
        for(int j=0;j<n2;j++){
            R[j]=A[q+j+1];
        }
        L[n1]=Integer.MAX_VALUE;
        R[n2]=Integer.MAX_VALUE;
        int i=0;
        int j=0;
        for(int k=p;k<(r+1);k++){
            if(L[i]<= R[j]){                
                A[k]=L[i];
                i=i+1;
            }
            else {
                A[k]=R[j];
                j=j+1;
                int numOFElements=n1-i; 
                inversions=inversions+numOFElements; // this counts inversion
            }
        }
    }

}

一部のケースでは機能しますが、他のケースでは間違った出力が得られます。何か不足している場合はお知らせください。

4

2 に答える 2

0

問題は、「反転」を「int」データ型として使用しているため、非常に大きな入力に対してオーバーフローすることです。代わりに「long」を使用してください。正常に動作するはずです。

于 2013-07-10T22:56:22.717 に答える
0

これは Cormen book と同じ実装です。しかし、この本では、配列のインデックスが 1 であると想定しています。多分これです。インデックスが 0 の配列があることを考慮して、コードを変更してみてください。

インデックスが 0 の場合、n1 変数は qp と等しいはずです

于 2013-07-05T03:19:20.553 に答える