[Scala][基礎アルゴリズム] 挿入ソート（２） シェル法

シェル法は、配列を飛び飛びの間隔でグルーピングして、各グループに単純挿入法を適用する操作を、間隔を狭めながら繰り返す。一回の操作ごとに、配列が整列された状態に近づいていく。

Wikipediaの説明： シェルソート

・一般に、キーの移動回数が単純挿入法より大幅に少なくなる

object ShellSort {

    // ソート対象列 array と、グルーピング間隔の配列 delta が与えられる
    def sort(array: Array[Int], delta: Array[Int]) = {
        // targetVal を適切な場所に挿入する
        // d はグルーピング間隔
        def insert(targetVal: Int, n: Int, d: Int) {
            if (n >= 0 && array(n) > targetVal) {
                array(n+d) = array(n)    // (*) キー移動
                insert(targetVal, n - d, d)
            } else {
                array(n+d) = targetVal
            }
        }

        for (d <- delta;
             i <- d until array.length) {
            insert(array(i), i - d, d)
        }
    }

    // main
    def main(args: Array[String]):Unit = {
        val array = Array(2,9,3,5,8,7,4,1,6)
        println("-*- ShellSortTest -*-")
        println("ソート前: " + array.toString)
        sort(array, Array(4,2,1)) // 4 -> 2 -> 1 と間隔を狭めていく
        println("ソート後: " + array.toString)
    }
}

// 実行結果

-*- ShellSortTest -*-
ソート前: Array(2, 9, 3, 5, 8, 7, 4, 1, 6)
ソート後: Array(1, 2, 3, 4, 5, 6, 7, 8, 9)

この例では、キーの移動(７行目)回数は11回。同じ配列を単純挿入法でソートした場合のキー移動回数は19回となる。