明解 Javaによるアルゴリズムとデータ構造 6-5_シェルソート

6-5 シェルソート

単純挿入ソートの特徴

  • ソート済みあるいは、それに近い状態では高速である
  • 挿入先が遠くはなれている場合、移動(代入)回数が多くなる

シェルソート

  • シェルソート shell sort は、単純挿入ソートの長所を活かしたまま、その短所を補う事によって、高速なソートを行うアルゴリズムである。
  • D.L.Shell が考案。
  • クイックソートが考案されるまで、最速だった。
  • 最初に離れた要素をグループ化しておおまかなソートを行い、そのグループを縮小しながらソートを繰り返す
    • このギャップの設定にはいくつかあるが、一般には Knuth の方法が取られる。
       1,\ 4,\ 13,\ 40,\ 121,\ \cdots,\ \frac{3^{k}-1}{2}
    • 初期のギャップがあまり大きくても無駄とわかっているため、 n / 9 を超えないようにする。
    • Knuth の方法の場合の時間計算量:
       O(n^{1.25})
      nが極めて小さい時以外は、
       O(n^{2})
      のソートアルゴリズムよりもコストが低い。
  • 安定ではない

ソースコード

  • 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]);
        }
    }
}
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]);
        }
    }
}

実行結果

  • 降順に並んでいるような状態からだと、後者のほうがコストが高いように見えた。なぜ?

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

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