1

挿入ソートのさまざまな実装に関していくつか質問があります。

実装1：

public static void insertionSort(int[] a) {
    for (int i = 1; i < a.length; ++i) {
        int key = a[i];
        int j   = i - 1;

        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            --j;
        }

        a[j + 1] = key;
    }
}

実装2：

public static void insertionSort(int[] a) {
    for (int i = 1; i < a.length; ++i) {
        for (int j = i; j > 0 && a[j - 1] > a[j]; --j) {
            swap(a, j, j - 1);
        }
    }
}

private static void swap(int[] a, int i, int j) {
    int tmp = a[i];

    a[i] = a[j];
    a[j] = tmp;
}

これが私の最初の質問です。最初のバージョンは2番目のバージョンよりも少し速いはずですが（割り当てが少ないため）、そうではありません（または少なくとも違いはごくわずかです）。しかし、なぜ？

次に、JavaのArrays.sort（）メソッドも2番目のアプローチを使用しているのではないかと思いました（おそらく、swapメソッドがさまざまな場所で使用されているため、コードが再利用されているためか、理解しやすいためです）。

実装3（binaryInsertionSort）：

    public static void binaryInsertionSort(int[] a) {
    for (int i = 1; i < a.length; ++i) {
        int pos            = Arrays.binarySearch(a, 0, i, a[i]);
        int insertionPoint = (pos >= 0) ? pos : -pos - 1;

        if (insertionPoint < i) {
            int key = a[i];

            // for (int j = i; i > insertionPoint; --i) {
            //     a[j] = a[j - 1];
            // }
            System.arraycopy(a, insertionPoint, a, insertionPoint + 1, i - insertionPoint);

            a[insertionPoint] = key;
        }
    }
}

バイナリ挿入は実用的なものですか、それとも理論的なものですか？小さなアレイでは、他のアプローチがはるかに高速であり、大きなアレイでは、mergesort/quicksortのパフォーマンスがはるかに優れています。

4

1 に答える 1

0
  1. 虚偽の申し立てを削除する
  2. 最初の 2 つの比較の回数は、外側のループの比較を除いて、1/2*n(n-1) です。
  3. これらのプログラムはどれも、自由に使える情報を利用しないため、そのままでは実際の作業にはあまり意味がありません。たとえば、内側のループにチェックを追加して、スワップが行われたかどうかを確認するのは簡単です。スワップが行われていない場合は、配列がソートされ、おそらくほとんどの作業を保存して終了できます。実際には、これらの種類の考慮事項が平均的なケースを支配する可能性があります。

Postscript Java に関する質問を見逃しました: Java のソートは非常に複雑なアルゴリズムであり、小さな配列の特殊なソート ケースや、クイックソートを使用して重い作業を行うなど、多くの特殊なケースを使用することを理解しています。

于 2010-01-28T12:12:00.743 に答える