明解 Javaによるアルゴリズムとデータ構造 6-5_シェルソート
6-5 シェルソート
単純挿入ソートの特徴
- ソート済みあるいは、それに近い状態では高速である
- 挿入先が遠くはなれている場合、移動(代入)回数が多くなる
シェルソート
- シェルソート shell sort は、単純挿入ソートの長所を活かしたまま、その短所を補う事によって、高速なソートを行うアルゴリズムである。
- D.L.Shell が考案。
- クイックソートが考案されるまで、最速だった。
- 最初に離れた要素をグループ化しておおまかなソートを行い、そのグループを縮小しながらソートを繰り返す
- 安定ではない
ソースコード
- gap はただただ 1/2 していくだけ
import java.util.Scanner; class ShellSort { static void shellSort(int[]a, int n) { int moveCnt = 0; for (int h = n / 2; h > 0; h /= 2) { for (int i = h; i < n; i++) { int j; int tmp = a[i]; for (j = i - h; j >= 0 && a[j] > tmp; j -= h) { a[j+h]=a[j]; moveCnt++; } a[j+h] = tmp; moveCnt++; } } System.out.println("交換回数: " + moveCnt); } 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(); } shellSort(x, nx); System.out.println("昇順にソートしました"); for (int i = 0; i < nx; i++) { System.out.println("x[" + i + "]: " + x[i]); } } }
- gap は Knuth 式
import java.util.Scanner; class ShellSort2 { static void shellSort(int[]a, int n) { int h; int moveCnt = 0; for (h = 1; h < n / 9; h = h * 3 + 1) { ; } for ( ; h > 0; h /= 3) { for (int i = h; i < n; i++) { int j; int tmp = a[i]; for (j = i - h; j >= 0 && a[j] > tmp; j -= h) { a[j+h]=a[j]; moveCnt++; } a[j+h] = tmp; moveCnt++; } } System.out.println("交換回数: " + moveCnt); } 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(); } shellSort(x, nx); System.out.println("昇順にソートしました"); for (int i = 0; i < nx; i++) { System.out.println("x[" + i + "]: " + x[i]); } } }
実行結果
- 降順に並んでいるような状態からだと、後者のほうがコストが高いように見えた。なぜ?
- 作者: 柴田望洋
- 出版社/メーカー: ソフトバンククリエイティブ
- 発売日: 2007/11/07
- メディア: 単行本
- 購入: 5人 クリック: 42回
- この商品を含むブログ (19件) を見る