数値の配列で反転を見つけるコードを作成しようとしています。Merge Sort を使用して正しく行うアルゴリズムを見てきましたが、ロジックに関して質問があります。
左と右の部分配列の反転、および 2 つの間の反転をカウントする必要があるのはなぜですか? 明らかにそれは正しいのですが、マージ ステップですべての反転を数えることができないのはなぜですか? マージを実行するすべてのレベルで、反転の数を直接数えることができ、2 倍のサイズの部分配列が生成された後、その 2 つの要素の相対的な順序は、後続のマージ ステップで決して変化しないことがわかります。つまり、最終的に反転にならない反転はカウントされません。では、ロジックの何が問題なのか、正しい答えが得られないからです。
必要に応じて、例やコードで詳しく説明できます。意図的にコードを含めなかったので、誰もこれが宿題だとは思わない.
編集：これまでのところ、ロジックに問題はありませんが、代わりに間違った答えにつながるコードのバグが見つかりました。
したがって、配列内の反転を見つける方法は次のとおりです。
private void findInversions(int begin, int end, int count) {
if (end - begin < 1)
return;
int middle = (begin + end) / 2;
findInversions(begin, middle, count);
System.out.println("But here count is " + count + " and I can't find why.");
findInversions(middle + 1, end, count);
count = mergeAndCount(begin, middle, end, count);
System.out.println("count now is: " + count);
}
mergeAndCount()メソッドは明らかな方法で機能します。
private int mergeAndCount(int begin, int middle, int end, int count) {
int[] result = new int[end - begin + 1];
int aptr = begin;
int bptr = middle + 1;
for (int i = 0; i < result.length; i++) {
if (aptr <= middle && bptr <= end) {
if (numbers[aptr] < numbers[bptr]) {
result[i] = numbers[aptr];
aptr++;
}
else {
// (a[aptr], b[bptr]) is an inversion here
count++;
System.out.println("Found: (" + numbers[aptr] + "," + numbers[bptr] + "). If you print 'count' here it'll be one. See: " + count);
result[i] = numbers[bptr];
bptr++;
}
}
else if (aptr > middle) {
result[i] = numbers[bptr];
bptr++;
}
else if (bptr > end) {
result[i] = numbers[aptr];
aptr++;
}
}
for (int i = 0; i < result.length; i++) {
numbers[begin + i] = result[i];
}
return count;
}
そして、 count をゼロに設定してメソッドを呼び出します: findInversions(0, numbers.length - 1, 0)。
明らかに問題は、countさまざまな再帰間でその値を保持しないことです。これは Java であるため、アンパサンドを付けて渡す必要はなく、その値を で返しますmergeAndCount()。ここで何が問題なのですか？