0

以下のマージソート反復実装がありますが、どういうわけか機能していません。デバッグしましたが、原因がわかりませんでした。

Merge'ing 関数は再帰的な場合と同じままで、配列の分割ロジックのみが異なります (私が正しければ)。

間違った方向に進んでいる場合は、修正してください。

4

2 に答える 2

2

同じオブジェクトを使用して異なる間隔を表現しようとすると問題があると思います: MergeSort_Iterative ループで、list1 に新しい要素を追加するときに、「情報」オブジェクトを一時変数として使用し、それを list1 コレクションに追加します。

Java では、すべてのオブジェクト変数が参照であるため、オブジェクトをコレクションに追加すると、オブジェクトのコピーを追加するのではなく、参照を変更して再度挿入することになります。

info.left = left;
info.right = mid;
list1.add(info);

info.left = mid + 1;
info.right = right;
list1.add(info);

2 つのオブジェクトが挿入を実行するために 2 つのオブジェクトを作成する必要があることを修正するには、次のようにします。

info = new MergePosInfo();
info.left = left;
info.right = mid;
list1.add(info);

info = new MergePosInfo();
info.left = mid + 1;
info.right = right;
list1.add(info);

一方、上記の問題が解決されたら、短い間隔から広い間隔、左から右の位置に list2 を反復処理する必要がありますが、アルゴリズムはその順序で list2 を生成していません。

MergeSort_Iterative を変更する必要があります。

public static void MergeSort_Iterative(int[] numbers, int left, int right) {
    int mid;
    if (right <= left)
        return;

    LinkedList<MergePosInfo> list1 = new LinkedList<MergePosInfo>();
    LinkedList<MergePosInfo> list2 = new LinkedList<MergePosInfo>();

    for(int i = left; i <= right; i+=2)
    {
        MergePosInfo info = new MergePosInfo();
        info.left = i;
        info.right = (i+1<=right)?(i+1):i;
        info.mid = -1;
        list1.add(info);
        list2.add(info);
    }

    int l = right-left+1;
    for(int partsSize = 2; partsSize <= l/2; partsSize*=2)
    {
        int ll1 =    list1.size();
        for(int i = 0; i < ll1; i+=2)
        {
            MergePosInfo info2 = new MergePosInfo();
            info2.left = list1.get(0).left;
            info2.right = list1.get(1).right;
            info2.mid = (info2.left+info2.right)/2;

            list1.remove(0);
            list1.remove(0);

            list1.add(info2);
            list2.addLast(info2);
        }
    }


    for (int i = 0; i < list2.size(); i++) {
        System.out.println("Merge [" + Integer.toString(list2.get(i).left) + " , "  + Integer.toString(list2.get(i).right) + "]" );
        DoMerge(numbers, list2.get(i).left, list2.get(i).mid+1,
                list2.get(i).right);
    }

}

DoMerge にいくつかの行を追加するだけでなく、

public static void DoMerge(int[] numbers, int left, int mid, int right) {
       int[] temp = new int[25];
       int i, left_end, num_elements, tmp_pos;

       left_end = (mid - 1);
       tmp_pos = left;
       num_elements = (right - left + 1);

       if(num_elements == 2)
       {
           if(numbers[left]>numbers[right])
           {
               int buffer = numbers[left];
               numbers[left] = numbers[right];
               numbers[right] = buffer;
           }
           return;
        }
       ...

ご覧のとおり、私が提供したソリューションは、「数値」の長さが 2^k の場合にのみ機能します。ご自身で修正してみてください。修正できない場合は、最後の変更を行います。

System.out.println("Merge [" + Integer.toString(list2.get(i).left) + " , " + Integer.toString(list2.get(i).right) + "]" ); を残しました。

マージソートがどのように機能するかを理解できるようにします。

于 2013-07-01T10:29:16.890 に答える
1 
            info.left = left;
            info.right = mid;
            list1.add(info);

            info.left = mid + 1;
            info.right = right;
            list1.add(info);

同じオブジェクトを操作しています。あなたがやっているのと同じように、反復ごとに異なるオブジェクトを使用してくださいinfo2

于 2013-07-01T10:34:04.043 に答える