1

InsertionSort と ShellSort という 2 つの異なる並べ替えの 2 つの実装があります。

それらは次のとおりです。

挿入ソート:

for (int pos = 0; pos < arrayToBeSorted.length; pos++) {
    for (int secondMarker = pos; secondMarker > 0; secondMarker--) {
        int currentValue = arrayToBeSorted[secondMarker];
        int valueBeingCheckedAgainst = arrayToBeSorted[secondMarker - 1];
        if (currentValue > valueBeingCheckedAgainst) {
            break;
        }
        arrayToBeSorted[secondMarker] = arrayToBeSorted[secondMarker - 1];
        arrayToBeSorted[secondMarker - 1] = currentValue;
    }
}

シェルソート:

for (int gap = a.length / a.length; gap > 0; gap = (gap / 2)) {
    for (int i = gap; i < a.length; i++) {
        int tmp = a[i];
        int j = i;
        for (; j >= gap && tmp < (a[j - gap]); j -= gap) {
            a[j] = a[j - gap];
        }
        a[j] = tmp;
    }
}

また、32000 個の整数を保持する整数の配列が 10 個あります。これらのクラスで静的な sortArray メソッドを呼び出す前に時間を取得します。結果は次のとおりです。

InsertionSort.sortArray の場合:

Solving array with: 32000 elements.
Time in milliseconds:264
Time in milliseconds:271
Time in milliseconds:268
Time in milliseconds:263
Time in milliseconds:259
Time in milliseconds:257
Time in milliseconds:258
Time in milliseconds:260
Time in milliseconds:259
Time in milliseconds:261

そして、ShellSort の場合:

Solving array with: 32000 elements.
Time in milliseconds:357
Time in milliseconds:337
Time in milliseconds:167
Time in milliseconds:168
Time in milliseconds:165
Time in milliseconds:168
Time in milliseconds:167
Time in milliseconds:167
Time in milliseconds:166
Time in milliseconds:167

では、なぜそれらの間にこれほどの違いがあるのでしょうか。それらは基本的に同じアルゴリズムですか？

また、ShellSort の最初の 2 回の実行に時間がかかり、残りの実行が速いというのはどうしてでしょうか?

これは 128000 要素の結果です。最初に InsertionSort をもう一度実行します。

Solving array with: 128000 elements.
Time in milliseconds:4292
Time in milliseconds:4267
Time in milliseconds:4241
Time in milliseconds:4252
Time in milliseconds:4253
Time in milliseconds:4248
Time in milliseconds:4261
Time in milliseconds:4260
Time in milliseconds:4333
Time in milliseconds:4261

シェルソート:

Solving array with: 128000 elements.
Time in milliseconds:5358
Time in milliseconds:5335
Time in milliseconds:2676
Time in milliseconds:2656
Time in milliseconds:2662
Time in milliseconds:2654
Time in milliseconds:2661
Time in milliseconds:2656
Time in milliseconds:2660
Time in milliseconds:2673

メソッドに渡す配列はまったく同じであり、かなりランダムであると確信しています。

4

1 に答える 1

1

挿入ソートでは、より複雑になっていますが、

for (int pos = 0; pos < arrayToBeSorted.length; pos++) {
    for (int secondMarker = pos; secondMarker > 0; secondMarker--) {
        int currentValue = arrayToBeSorted[secondMarker];
        int valueBeingCheckedAgainst = arrayToBeSorted[secondMarker - 1];
        if (currentValue > valueBeingCheckedAgainst) {
            break;
        }
        arrayToBeSorted[secondMarker] = arrayToBeSorted[secondMarker - 1];
        arrayToBeSorted[secondMarker - 1] = currentValue;
    }
}

内側のループで配列から値を読み取り、前の位置の値が小さくない間に、2 つの値を配列に書き込みます。

シェルソートでは、

for (int i = gap; i < a.length; i++) {
    int tmp = a[i];
    int j = i;
    for (; j >= gap && tmp < (a[j - gap]); j -= gap) {
        a[j] = a[j - gap];
    }
    a[j] = tmp;
}

内側のループの外側で一度配置される値を読み取り、内側のループ本体に 1 回だけ書き込み、内側のループの後に値を 1 回だけ書き込みます。

その方が効率的で、シェルのソートが高速であることは理解できます。最初の 2 つのシェル ソートが遅いのは、おそらくラッピングが原因です。

for (int gap = a.length / a.length; gap > 0; gap = (gap / 2)) {

gapを 1 に置き換えることができ、ラッピング ループが排除されることに気付く前に、JIT をしばらく混乱させます。

于 2013-05-11T21:13:04.693 に答える