明解 Javaによるアルゴリズムとデータ構造 6-4_単純挿入ソート

6-4 単純選択ソート straight insertion sort

  • 『原列の先頭要素を、目的列内の適切な位置に挿入』を、n - 1 回繰り返す

    • トランプのカード並べに似たソート(7並べをイメージしてね)
  • 実装としては、

    1. 『左隣の要素が、現在着目している要素より大きい限り、その値を代入』。 tmp に a[i] を保持しつつ、繰り返し用変数 j に i - 1 を代入しておき、以下のいずれか一方を満たせば終了。
      1. 目的列の左端に達する
      2. tmpと等しいか小さいキーを持つ a[j] に出会う
    2. ド・モルガンの法則から、以下2つの条件が両方成立しているあいだ繰り返す
      1. j が 0 より大きい
      2. a[j - 1] の値が tmp より大きい
    3. 操作が完了すると、a[j] に tmp を単純挿入する
  • 飛び越えた要素の交換は実施しないので、安定なアルゴリズム

  • 比較回数: 注目要素を目的列に挿入する際の、平均比較回数
    \displaystyle \sum_{k=1}^{n-1} \frac{k}{2}} = \frac{n(n-1)}{4}

疑問

本だと 、時間計算量
\displaystyle \frac{{n}^2}{2}}
なんだけど、どういう計算なんだろう。

ソースコードと実行結果

import java.util.Scanner;

class InsertionSort {
    static void insertionSort(int[] a, int n) {
        int ccnt = 0; // 比較回数
        int scnt = 0; // 挿入回数
        for (int i = 1; i < n; i++) {
            System.out.println("パス: " + i);
            for (int e : a) {
                System.out.printf("%3d%c", e, (e == a[i]) ? '*' : ' '); // '*' -> ソートする要素
            }
            System.out.println();

            int j;
            int tmp = a[i];

            for (j = i; j > 0 && a[j - 1] > tmp; j--) {
                a[j] = a[j - 1];
                scnt++;
                for (int e : a) {
                    System.out.printf("%3d%c", e, 
                                        (e == a[j - 1]) ? '+'           // '+' -> コピーされる要素
                                        : (e == a[j]) ? '-' : ' ');     // '-' -> 上書かれる要素
                }
                System.out.println();
                ccnt++;
            }
            a[j] = tmp;
            for (int e : a) {
                System.out.printf("%3d%c", e, ' ');
            }
            System.out.println();
            
            System.out.println("比較回数: " + ccnt);
            System.out.println("交換回数: " + scnt);
        }
    }

    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        System.out.println("単純挿入ソート");
        System.out.print("要素数: ");

        int nx = stdIn.nextInt();
        int[] x = new int[nx];

        for (int i = 0; i < nx; i++) {
            System.out.print("x[" + i + "]: ");
            x[i] = stdIn.nextInt();
        }

        insertionSort(x, nx);

        System.out.println("昇順にソートしました");
        for (int i = 0; i < nx; i++) {
            System.out.println("x[" + i + "]=" + x[i]);
        }
    }
}
単純挿入ソート
要素数: 4
x[0]: 4
x[1]: 3
x[2]: 2
x[3]: 1
パス: 1
  4   3*  2   1 
  4+  4+  2   1 
  3   4   2   1 
比較回数: 1
交換回数: 1
パス: 2
  3   4   2*  1 
  3   4+  4+  1 
  3+  3+  4   1 
  2   3   4   1 
比較回数: 3
交換回数: 3
パス: 3
  2   3   4   1*
  2   3   4+  4+
  2   3+  3+  4 
  2+  2+  3   4 
  1   2   3   4 
比較回数: 6
交換回数: 6
昇順にソートしました
x[0]=1
x[1]=2
x[2]=3
x[3]=4
  • 番兵法 sentinel を適用して、終了条件をひとつにした版のメソッド
class InsertionSortSen {
    static void insertionSort(int[] a, int n) {
        int ccnt = 0; // 比較回数
        int scnt = 0; // 挿入回数
        for (int i = 2; i < n; i++) {
            System.out.println("パス: " + i);
            for (int e : a) {
                System.out.printf("%3d%c", e, (e == a[i]) ? '*' : ' '); // '*' -> ソートする要素
            }
            System.out.println();

            int j;
            int tmp = a[i] = a[0];

            for (j = i; a[j - 1] > tmp; j--) {
                a[j] = a[j - 1];
                scnt++;
                for (int e : a) {
                    System.out.printf("%3d%c", e, 
                                        (e == a[j - 1]) ? '+'           // '+' -> コピーされる要素
                                        : (e == a[j]) ? '-' : ' ');     // '-' -> 上書かれる要素
                }
                System.out.println();
                ccnt++;
            }
            if (j > 0) {
                a[j] = tmp;
            }
            for (int e : a) {
                System.out.printf("%3d%c", e, ' ');
            }
            System.out.println();
            
            System.out.println("比較回数: " + ccnt);
            System.out.println("交換回数: " + scnt);
        }
    }
}

2分挿入ソート binary insertion sort

  • 配列が大きくなるにつれ、要素の挿入に要する比較・代入のコストも大きくなる。挿入すべき位置の探索に、二分探索を使うことでコスト削減を実現している。
    • 代入に関しては軽くなってない。

ソースコード

import java.util.Scanner;

class BinaryInsertionSort {
    static void insertionSort(int[] a, int n) {
        for (int i = 1; i < n; i++) {
            System.out.println("パス: " + i);

            int j = binarySearch(a, a[i], i - 1);
            int tmp = a[i];
            
            for (int k = 0; k < n; k++) {
                System.out.printf("%3d%c", a[k],
                    (k < i) ? '-'           // '-' -> 目的列
                    : (k == i) ? '*'        // '*' -> ソート対象
                    : ' ');                 // ' ' -> 原列
            }
            System.out.println();
            
            for (int k = i; k > j; k--) {
                a[k] = a[k - 1];
            }
            
            a[j] = tmp;
            for (int k = 0; k < n; k++) {
                System.out.printf("%3d%c", a[k],
                    (k < j) ? '-'           // '-' -> 目的列
                    : (k == j) ? '*'        // '-' -> ソート対象の挿入先
                    : (k < i + 1) ? '-'     // '-' -> 目的列
                    : ' ');                 // ' ' -> 原列
            }
            System.out.println();
        }
    }

    /**
     * ある要素が、既存の昇順ソート済int配列のどのインデックスに挿入されるべきか、あるべきインデックスを返すメソッド
     * 
     * @param a
     * @param key
     * @param tailIdx
     * @return 挿入すべきインデックス
     */
    static int binarySearch(int[] a, int key, int tailIdx) {
        int headIdx = 0;
        int centerIdx = -1;
        int index = -1;
        
        while (headIdx <= tailIdx) {
            centerIdx = (headIdx + tailIdx) / 2;
            if (a[centerIdx] == key) {
                index = centerIdx + 1;          // 既に同値が存在すれば、次のインデックスを返す
                break;
            } else if (key < a[centerIdx]) {    // keyが前方に存在
                tailIdx = centerIdx - 1;
                index = centerIdx;              // 現在のcenterIdxを代入
            } else {                            // keyが後方に存在
                headIdx = centerIdx + 1;
                index = headIdx;                // 次のheadIdxを代入
            }
        }
        return index;
    }

    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        System.out.println("2分挿入ソート");
        System.out.print("要素数: ");

        int nx = stdIn.nextInt();
        int[] x = new int[nx];

        for (int i = 0; i < nx; i++) {
            System.out.print("x[" + i + "]: ");
            x[i] = stdIn.nextInt();
        }

        insertionSort(x, nx);

        System.out.println("昇順にソートしました");
        System.out.println("-------------");
        for (int i = 0; i < nx; i++) {
            System.out.println("x[" + i + "]=" + x[i]);
        }
    }
}
  • 実行結果

2分挿入ソート
要素数: 10
x[0]: 9
x[1]: 1
x[2]: 4
x[3]: 5
x[4]: 3
x[5]: 8
x[6]: 4
x[7]: 58
x[8]: 7
x[9]: 6
パス: 1
  9-  1*  4   5   3   8   4  58   7   6 
  1*  9-  4   5   3   8   4  58   7   6 
パス: 2
  1-  9-  4*  5   3   8   4  58   7   6 
  1-  4*  9-  5   3   8   4  58   7   6 
パス: 3
  1-  4-  9-  5*  3   8   4  58   7   6 
  1-  4-  5*  9-  3   8   4  58   7   6 
パス: 4
  1-  4-  5-  9-  3*  8   4  58   7   6 
  1-  3*  4-  5-  9-  8   4  58   7   6 
パス: 5
  1-  3-  4-  5-  9-  8*  4  58   7   6 
  1-  3-  4-  5-  8*  9-  4  58   7   6 
パス: 6
  1-  3-  4-  5-  8-  9-  4* 58   7   6 
  1-  3-  4-  4*  5-  8-  9- 58   7   6 
パス: 7
  1-  3-  4-  4-  5-  8-  9- 58*  7   6 
  1-  3-  4-  4-  5-  8-  9- 58*  7   6 
パス: 8
  1-  3-  4-  4-  5-  8-  9- 58-  7*  6 
  1-  3-  4-  4-  5-  7*  8-  9- 58-  6 
パス: 9
  1-  3-  4-  4-  5-  7-  8-  9- 58-  6*
  1-  3-  4-  4-  5-  6*  7-  8-  9- 58-
昇順にソートしました
-------------
x[0]=1
x[1]=3
x[2]=4
x[3]=4
x[4]=5
x[5]=6
x[6]=7
x[7]=8
x[8]=9
x[9]=58

疑問

  • テキストだと、2分挿入ソートは安定ではないと書いているが、安定性を保持したまま実装できてる気がする
    • なんか間違えてる?

回答

  • 実装によりけりっぽい。ちょっと、テキストさん、断言せんといてや・・・

    挿入ソートの改良で、挿入するデータの前ではソートが済んでいるという性質を利用して、挿入する箇所を二分探索するというものである。データの量が少ないときにはあまり効果がないが、多いときには比較回数が少なくなる。探索アルゴリズムによっては不安定なソートになるが、工夫により安定させることが可能である。
    挿入ソート - Wikipedia

明解 Javaによるアルゴリズムとデータ構造

明解 Javaによるアルゴリズムとデータ構造