明解 Javaによるアルゴリズムとデータ構造 6-4_単純挿入ソート
6-4 単純選択ソート straight insertion sort
『原列の先頭要素を、目的列内の適切な位置に挿入』を、n - 1 回繰り返す
- トランプのカード並べに似たソート(7並べをイメージしてね)
実装としては、
- 『左隣の要素が、現在着目している要素より大きい限り、その値を代入』。 tmp に a[i] を保持しつつ、繰り返し用変数 j に i - 1 を代入しておき、以下のいずれか一方を満たせば終了。
- 目的列の左端に達する
- tmpと等しいか小さいキーを持つ a[j] に出会う
- ド・モルガンの法則から、以下2つの条件が両方成立しているあいだ繰り返す
- j が 0 より大きい
- a[j - 1] の値が tmp より大きい
- 操作が完了すると、a[j] に tmp を単純挿入する
- 『左隣の要素が、現在着目している要素より大きい限り、その値を代入』。 tmp に a[i] を保持しつつ、繰り返し用変数 j に i - 1 を代入しておき、以下のいずれか一方を満たせば終了。
飛び越えた要素の交換は実施しないので、安定なアルゴリズム
- 比較回数: 注目要素を目的列に挿入する際の、平均比較回数
疑問
本だと 、時間計算量
なんだけど、どういう計算なんだろう。
ソースコードと実行結果
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
- 作者: 柴田望洋
- 出版社/メーカー: ソフトバンククリエイティブ
- 発売日: 2007/11/07
- メディア: 単行本
- 購入: 5人 クリック: 42回
- この商品を含むブログ (19件) を見る