3

マージソートアルゴリズムのマージ方法について質問があります。以下のコードをhttp://algs4.cs.princeton.edu/22mergesort/Merge.java.htmlからコピーしました。なぜ正しいサブ配列をコピーする必要があるのか​​ 理解できません。

この文

if (i > mid) index[k] = aux[j++];

右のサブ配列を右のサブ配列の上にコピーします。したがって、基本的に同じ値を上書きします。もし私がその中間を越えたなら、私は感じる

  1. 左のサブ配列値は完全にソートされています。
  2. 右側のサブ配列も j までソートされます。
  3. j の後のすべてのエントリ (j を含む) は既にソートされており、補助配列と元の配列 (a) は同じエントリを持っています。

そのため、i が mid を超えた場合、copy to right サブ配列ステートメントを廃止できるようです。

または、ユースケースが不足している可能性があります。あなたがそれを理解できるかどうか私に知らせてください。

// code begins

private static void merge(Comparable[] a, int[] index, int[] aux, int lo, int mid, int hi) {

    // copy to aux[]
    for (int k = lo; k <= hi; k++) {
        aux[k] = index[k]; 
    }

    // merge back to a[]
    int i = lo, j = mid+1;
    for (int k = lo; k <= hi; k++) {
        if      (i > mid)                    index[k] = aux[j++];
        else if (j > hi)                     index[k] = aux[i++];
        else if (less(a[aux[j]], a[aux[i]])) index[k] = aux[j++];
        else                                 index[k] = aux[i++];
    }
}
4

1 に答える 1

1

私はあなたが正しいと信じています-あなたが指摘した正確な理由から、そのコピー手順は不要に思えます。

これは、ソートする 2 つの配列が入力配列内で互いに隣接して格納されていなかった古いバージョンのマージ関数のアーティファクトである可能性があります。入力配列が 2 つの独立した配列に格納されている場合、未使用のすべての要素を一方の配列から結果の配列に移動するために、もう一方の配列が使い果たされた後に最後のコピー手順が必要になります。要素が入力配列に格納される方法により、この手順が必要ない可能性があることは間違いありません。

お役に立てれば！

于 2013-06-06T18:32:24.387 に答える