0

マージソートを使用した比較の数は、比較の数を返すマージソート2クラス/メソッドでは正しくないと思います。マージ ソート 2 はマージ ソートに似ていますが、比較の量を返すだけです。以下は私のデモです。4 つの整数 {2,55,1,45} の配列があり、プログラムを実行すると 8 つの比較が返されます。これが正しいかどうか、または私が間違っていることを誰かが確認できますか?

私のデモ:

    ArrayInts[] myInts2 = new ArrayInts[4];

    myInts2[0] = new ArrayInts(2);
    myInts2[1] = new ArrayInts(55);
    myInts2[2] = new ArrayInts(1);
    myInts2[3] = new ArrayInts(45);

    MergeSort.mergeSort(myInts2, 0, 3);

    System.out.println("Sorted using Merge Sort: ");


    for (int index = 0; index < myInts2.length; index++) {
        System.out.println(myInts2[index]);
    }

    System.out.println("Number of comps using Merge Sort: " + MergeSort2.mergeSort2(myInts2, 0, 3));
    System.out.println(" ");

私のマージソート2クラス/メソッド:

 public class MergeSort2 {
 private static long comp=0;

public static <T extends Comparable<? super T>> long mergeSort2(T[] data, int min, int max) {
    T[] temp;
    int index1, left, right;


    //return on list of length one

    if (min == max) {
        return comp;
    }

    //find the length and the midpoint of the list

    int size = max - min + 1;
    int pivot = (min + max) / 2;
    temp = (T[]) (new Comparable[size]);

    mergeSort2(data, min, pivot); //sort left half of list
    mergeSort2(data, pivot + 1, max); //sort right half of list

    //copy sorted data into workspace

    for (index1 = 0; index1 < size; index1++) {
        temp[index1] = data[min + index1];
    }

    //merge the two sorted lists

    left = 0;
    right = pivot - min + 1;
    for (index1 = 0; index1 < size; index1++) {
        comp++;
        if (right <= max - min) {

            if (left <= pivot - min) {

                if (temp[left].compareTo(temp[right]) > 0) {

                    data[index1 + min] = temp[right++];
                } else {
                    data[index1 + min] = temp[left++];
                }
            } else {
                data[index1 + min] = temp[right++];
            }
        } else {
            data[index1 + min] = temp[left++];
        }
    }


    return comp;

    }

    }
4

2 に答える 2

0

あなたが示している比較の数は、あなたが私たちに与えた方法に対して正しいものです. 指定したメソッドに長さの配列4が渡されると、行comp++;が 8 回呼び出されます。説明させてください。

まず、pivot=1. これらの行は 2 つの再帰呼び出しを行います。

mergeSort2(data, min, pivot); //sort left half of list
mergeSort2(data, pivot + 1, max); //sort right half of list

これらの各呼び出しが 2 つの追加の入れ子になった再帰呼び出しを完了するとcomp、for ループが に等しい反復回数を実行するため、2 ずつインクリメントされますsize。これらの呼び出しの両方でsize=2、したがって、呼び出し 1 の後、comp=2、および呼び出し 2 の後、comp=4. これらの再帰呼び出しのそれぞれは、順番にさらに 2 つの再帰呼び出しを行います。ただし、これらの呼び出しのそれぞれでmin==max、メソッドは on を返し、return comp;インクリメントする行に到達しないためcompです。

最後に、最初の 2 回の再帰メソッド呼び出しが返された後、for ループのインクリメントcompがさらに 4 回呼び出されsize=4ます。したがって、comp = 4 + 4は 8 です。

それが紛らわしい場合は、への各呼び出しの ( min, ) で私の答えを説明します。maxmergesort2()

/* 1. */ (min=0, max=3) -> size=4, comp = comp + 4;
/* 2. */     (min=0, max=1) -> size=2, comp = comp + 2;
/* 3. */         (min=0, max=0) -> size=0, comp = comp + 0;
/* 4. */         (min=1, max=1) -> size=0, comp = comp + 0;
/* 5. */     (min=2, max=3) -> size=2, comp = comp + 2;
/* 6. */         (min=2, max=2) -> size=0, comp = comp + 0;
/* 7. */         (min=3, max=3) -> size=0; comp = comp + 0;

/* TOTAL. */  comp = 0 + 0 + 2 + 0 + 0 + 2 + 4; comp = 8

うまくいけば、私はここで自分自身を明確にしました！

edit1: BevynQ の答えは正しいです。私の答えは、あなたのコードが 8 を返す理由に焦点を当てていますが、彼の答えは、並べ替えメソッドが比較を誤ってカウントしている理由に焦点を当てています。

edit2:コードをコピーしてエディターに直接貼り付け、BevynQ が追加した 1 行の変更を行いました。私のコードは意図したとおりに動作しますが、あなたと同じ結果が得られません。おそらく何か他のものが誤って変更されたのでしょうか？

于 2013-09-09T02:24:16.913 に答える