0

これは、Javaで機能するmergesortのmergeの実装です。

void merge(int[] numbers, int low, int mid, int high) {
    int helper[] = new int[numbers.length];
    for (int i = low; i <= high; i++) {
         helper[i] = numbers[i];
    }

    int lowone = low;
    int lowtwo = mid + 1;
    int count = low;

    while (lowone <= mid || lowtwo <= high) {
        if (lowone <= mid && lowtwo <= high) {
            if (helper[lowone] <= helper[lowtwo]) {
                numbers[count] = helper[lowone];
                lowone++;
            } else {
                numbers[count] = helper[lowtwo];
                lowtwo++;
            }
        }
        else if (lowone <= mid) {
              numbers[count] = helper[lowone];
              lowone++;
            }
        else {
              numbers[count] = helper[lowtwo];
              lowtwo++;

        }
       count++;
    }
}
//msort algorithm in case it's relevant
void msort(int[] arr, int low, int high) {
    if (low < high) {
        int mid = (low + high)/2;

        msort(arr, low, mid);
        msort(arr, mid + 1, high);

        merge(arr, low, mid, high);
    }
}

マージの最初の試みでは、配列の後半に中間インデックスを含めるのではなく、中間インデックスを含めるようにしました。関連するコードは次のとおりです（上記からの変更は4つだけであることに注意してください）。

    int lowtwo = mid;

    while (lowone < mid || lowtwo <= high) {
        if (lowone < mid && lowtwo <= high) {
            if (helper[lowone] <= helper[lowtwo]) {
                numbers[count] = helper[lowone];
                lowone++;
            } else {
                numbers[count] = helper[lowtwo];
                lowtwo++;
            }
        }
        else if (lowone < mid) {
              numbers[count] = helper[lowone];
              lowone++;
        }
        else {
              numbers[count] = helper[lowtwo];
              lowtwo++;   
        }

msort（上記）で使用される変更されたバージョンは、リストを正しくソートしません。当たり前のことかもしれませんが、なぜうまくいかないのか理解できないようです。

4

2 に答える 2

1

これはmsort(...)、2番目のサブアレイ（in）の中点とのマージを実行する前に、最初のサブアレイ（in）の中点で2つのサブリストを並べ替えたためですmerge(...)。

最も簡単な例を見てください

[2,1]

そのように分割されます（mid ==（（0 + 1）/ 2）== 0であるため）

[2]と[1]

どのmsortが自明にソートするか

[2]と[1]

しかし、その後、マージの2番目のリストにmidを配置することにより、実際には次のようにマージします。

[]と[2,1]

これは明らかに[2,1]になりますが、これは間違っています。

中点の配置は、2つのサブアレイの分割とマージの両方で一貫している必要があります。

于 2012-12-30T05:34:36.150 に答える
1

問題は、マージでmidの意味を変更するために発生します。それを見る最も簡単な方法は例です。インデックスを持つ配列があるとしましょう：

[0 1 2 3 4]

msortを呼び出すと、低の場合は0、高の場合は4を渡します。つまり、midは2として計算されます。これで、配列がそのように分割されました（メモリ内ではなく、論理的に）。

[0 1 2] [3 4]

これで、mergeが呼び出されると、配列1の最後のインデックスであるmidが2で渡されます。ただし、変更されたコードでは、midを配列2の開始インデックスとして扱います。これにより、2つの配列は次のようになります。

[0 1] [2 3 4]

これは、すべてがそれをどのように扱うかとは異なります。これが失敗する例は、2つの配列（並べ替え後）が次のようになっている場合です（数値は値であり、インデックスではありません）。

[8 12 14] [7 11]

ただし、midの解釈では、配列は次のとおりです。

[8 12] [14 7 11]

ソートされなくなりました。したがって、マージ機能は機能しません。

于 2012-12-30T05:16:05.663 に答える