2010年1月21日木曜日

[Scala][基礎アルゴリズム] 挿入ソート(1) 単純挿入法

単純挿入法(シャトル整列法)とは

配列データ a[1], ..., a[n] があって、仮に a[i] より前の部分は整列しているものとする。
(1)a[i] の値を w としよう。
(2)a[i-1] から左へ、w との比較を行っていき、w より小さいキーに出会うまで配列データを一つ後ろへシフトさせる操作を繰り返す。
(3)w より小さいキーに出会ったら、その直後が w を格納する位置である。
(1)~(3)を配列の最後まで繰り返す。

というもの。

(『データ構造』P120 より)


object StraightInsertionSort {

def sort(array: Array[Int]) = {
// targetVal を適切な場所に挿入する
def insert(targetVal: Int, n: Int) {
if (n >= 0 && array(n) > targetVal) {
array(n+1) = array(n)
insert(targetVal, n - 1)
} else {
array(n+1) = targetVal
println(targetVal + " inserted. " + array.toString)
}
}

for (i <- 1 until array.length) {
insert(array(i), i - 1)
}
}

// main
def main(args: Array[String]):Unit = {
val array = Array(2,9,3,5,8,7,4,1,6)
println("-*- StraightInsertionTest -*-")
println("ソート前: " + array.toString)
sort(array)
println("ソート後: " + array.toString)
}
}


// 実行結果

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

0 件のコメント:

コメントを投稿