2

Javaでマージソートを使用して、数値の配列をソートしようとしています。この場合、配列はnumBarsです。30個の数字の小さな配列を作成し、コンソールからの出力を添付しました。マージメソッドを追跡して、インデックスの問題が発生する理由を確認します。私はどこかで1ずれていると思いますが、私の論理がどこに向かっているのか理解できないようです。

public void mergeSort() {
        mergeSortHelper(numBars, 0);
        System.out.println(Arrays.toString(numBars));
    }

    public void mergeSortHelper(int[] theArray, int leftIndex) {

        //split the list in half
        int mid = theArray.length/2;
        if (mid < 1) {
            return;
        } else {
            System.out.println("Left Index is originally: " + leftIndex);
            int[] left = Arrays.copyOfRange(theArray, 0, mid);
            int[] right = Arrays.copyOfRange(theArray, mid, theArray.length);
            //sort the lower half
            mergeSortHelper(left, leftIndex);
            mergeSortHelper(right, leftIndex + left.length);
            //merge them together
            merge(left, right, leftIndex);
            System.out.println("Left Index is now: " + leftIndex);
            System.out.println("Right Index is now: " + (leftIndex + mid));
            System.out.println(Arrays.toString(numBars));
            left = Arrays.copyOfRange(numBars, leftIndex, leftIndex + mid);
            right = Arrays.copyOfRange(numBars, leftIndex + mid, leftIndex + mid + right.length);
        }
    }

    public void merge(int[]a, int[]b, int leftIndex) {
        int i = 0;
        int j = 0;
        int result = leftIndex;
        while (i < a.length && j < b.length) {
            //System.out.println("Comparing from A: " + a[i] + " Comparing from B: " + b[i]);
            if (a[i] < b[j]) {
                theCanvas.wait(theDelay);
                theCanvas.eraseRectangle(graphWidth + i * barWidth, graphHeight - barScale * numBars[i], barScale, barScale * numBars[i]);
                numBars[result] = a[i];
                result++;
                theCanvas.fillRectangle(graphWidth + i * barWidth, graphHeight - barScale * numBars[i], barScale, barScale * numBars[i]);
                i++;
            } else {
                theCanvas.wait(theDelay);
                theCanvas.eraseRectangle(graphWidth + j * barWidth, graphHeight - barScale * numBars[j], barScale, barScale * numBars[j]);
                numBars[result] = b[j];
                result++;
                theCanvas.fillRectangle(graphWidth + j * barWidth, graphHeight - barScale * numBars[j], barScale, barScale * numBars[j]);
                j++;

            }
            //System.out.println("First Loop, Comparing Size" + Arrays.toString(output));
        }
        while (i < a.length) {
            numBars[result] = a[i];
            result++;
            i++;
            //System.out.println("Second Loop, Finishing A array" + Arrays.toString(output));
        }

        while(j < b.length) {
            numBars[result] = b[j];
            result++;
            j++;
            //System.out.println("Third Loop, Finishing B array" + Arrays.toString(output));
        }
        //System.out.println(Arrays.toString(output));
    }

コンソール出力：

Left Index is originally: 0
Left Index is originally: 0
Left Index is originally: 0
Left Index is originally: 1
Left Index is now: 1
Right Index is now: 2
[10, 50, 55, 99, 18, 9, 46, 80, 37, 35, 69, 77, 34, 53, 53]
Left Index is now: 0
Right Index is now: 1
[10, 55, 50, 99, 18, 9, 46, 80, 37, 35, 69, 77, 34, 53, 53]
Left Index is originally: 3
Left Index is originally: 3
Left Index is now: 3
Right Index is now: 4
[10, 55, 50, 18, 99, 9, 46, 80, 37, 35, 69, 77, 34, 53, 53]
Left Index is originally: 5
Left Index is now: 5
Right Index is now: 6
[10, 55, 50, 18, 99, 9, 46, 80, 37, 35, 69, 77, 34, 53, 53]
Left Index is now: 3
Right Index is now: 5
[10, 55, 50, 9, 46, 99, 18, 80, 37, 35, 69, 77, 34, 53, 53]
Left Index is now: 0
Right Index is now: 3
[10, 55, 50, 99, 18, 9, 46, 80, 37, 35, 69, 77, 34, 53, 53]
Left Index is originally: 7
Left Index is originally: 7
Left Index is originally: 7
Left Index is now: 7
Right Index is now: 8
[10, 55, 50, 99, 18, 9, 46, 37, 80, 35, 69, 77, 34, 53, 53]
Left Index is originally: 9
Left Index is now: 9
Right Index is now: 10
[10, 55, 50, 99, 18, 9, 46, 37, 80, 35, 69, 77, 34, 53, 53]
Left Index is now: 7
Right Index is now: 9
[10, 55, 50, 99, 18, 9, 46, 35, 69, 80, 37, 77, 34, 53, 53]
Left Index is originally: 11
Left Index is originally: 11
Left Index is now: 11
Right Index is now: 12
[10, 55, 50, 99, 18, 9, 46, 35, 69, 80, 37, 34, 77, 53, 53]
Left Index is originally: 13
Left Index is now: 13
Right Index is now: 14
[10, 55, 50, 99, 18, 9, 46, 35, 69, 80, 37, 34, 77, 53, 53]
Left Index is now: 11
Right Index is now: 13
[10, 55, 50, 99, 18, 9, 46, 35, 69, 80, 37, 53, 53, 77, 34]
Left Index is now: 7
Right Index is now: 11
[10, 55, 50, 99, 18, 9, 46, 77, 34, 53, 53, 80, 37, 35, 69]
Left Index is now: 0
Right Index is now: 7
[10, 55, 50, 80, 37, 35, 69, 77, 34, 53, 53, 99, 18, 9, 46]
[10, 55, 50, 80, 37, 35, 69, 77, 34, 53, 53, 99, 18, 9, 46]

どんな助けでも大歓迎です！ありがとう！

4

1 に答える 1

2 
} else {
    System.out.println("Left Index is originally: " + leftIndex);
    int[] left = Arrays.copyOfRange(theArray, 0, mid);
    int[] right = Arrays.copyOfRange(theArray, mid, theArray.length);
    //sort the lower half
    mergeSortHelper(left, leftIndex);
    mergeSortHelper(right, leftIndex + left.length);
    //merge them together
    merge(left, right, leftIndex);
    System.out.println("Left Index is now: " + leftIndex);
    System.out.println("Right Index is now: " + (leftIndex + mid));
    System.out.println(Arrays.toString(numBars));
    left = Arrays.copyOfRange(numBars, leftIndex, leftIndex + mid);
    right = Arrays.copyOfRange(numBars, leftIndex + mid, leftIndex + mid + right.length);
}

最後に、とに値をコピーする場合、これらnumBarsは直後にスコープ外になり、ガベージコレクションされるため、まったく意味がありません。leftright

呼び出し元では、ソートする必要のある配列は変更されません。numBarsマージされた値を引数である配列にコピーする必要がありtheArrayます。これにより、呼び出し元がマージするときに、並べ替えられた配列がマージされます。

したがって、elseブロックの最後の2行を次のように置き換えます

for(int i = 0; i < mid; ++i) {
    theArray[i] = numBars[leftIndex + i];
}
for(int i = mid; i < mid + left.length; ++i) {
    theArray[i] = numBars[leftIndex + i];
}

マージ結果を、呼び出し元が渡したのと同じオブジェクトにコピーします。

ただし、マージ結果を引数として配置する配列を渡した場合は、コードがはるかにクリーンになりますmerge。

于 2012-12-11T00:57:08.893 に答える