[Scala][基礎アルゴリズム] 選択ソート（１） 単純選択法

地味に、基礎アルゴリズムをScalaで写経していこうシリーズ。
忘れかけてるアルゴリズムの復習とScalaの文法練習と、一石二鳥をねらってみる。つもり^^。

教科書には学部の頃使っていた『データ構造』を使う。なつかしい。

関数型っぽいエレガント（ていうんだっけ）なコードにほど遠いのはぬるい目で、バグは厳しい（冷たい？）目で見ていただければ。
なるべく var を使わない（代入しない）、ということだけ気にしよう。
あとできるだけimmutableに、インデックスループより再帰、というのも鉄則なのだろうけれど、ムダづかい・・・という感覚が抜けない。Cの人とかがJavaを見るとこういう感じなんだろうか。実際はどうなんだろ。

==

定番のソートからスタートするよ（誰だ）。

単純選択法は、名前の通り選択ソートの一番単純なタイプ。
「(1)入力キーの並びを順に並べ、(2)最小のキーの位置を知り、(3)先頭のキーと入れ替える。その後は、２番目以降のキー列について同様のことを行う。」
・キーの比較回数はO(n^2)
・キーの交換回数はn-1回ですむ

object StraightSort {

    // ソート関数。sortInnerを呼び出すだけのエントリポイント。
    def sort(array: Array[Int]): Array[Int] = sortInner(array, 0)

    // 配列のstart番目～最後の要素をソートする, 肝となるメソッド
    private def sortInner(array: Array[Int], start: Int): Array[Int] = {
        if(array.length == 0 || start == array.length-1) array
        else sortInner(swap(array, start, findMinIdx(array, start, start+1)), start+1)
    }

    // 配列のidx番目以降の要素のうち、最小のもののインデックスを返す
    private def findMinIdx(array: Array[Int], minIdx: Int, idx: Int): Int = {
        if (idx == array.length) minIdx
        else if (array(idx) < array(minIdx)) findMinIdx(array, idx, idx+1)
        else findMinIdx(array, minIdx, idx+1)
    }

    // swap関数
    private def swap(array: Array[Int], x: Int, y: Int): Array[Int] = {
        val tmp = array(x); array(x) = array(y); array(y) = tmp; array
    }

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

// 実行結果

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

しかしほんとに地味だな。

==== 追記(2010.01.17) ====

2,3日たって見直すと、あまりにひどいコードだったので少しだけ修正。arrayの引渡しを（インナーメソッドに変更して）なくして、副作用をもつ関数はUnitに統一。

object StraightSort2 {
    // sort関数
    def sort(array: Array[Int]) {
        // 配列のidx番目以降の要素のうち、最小のもののインデックスを返す
        def findMinIdx(minIdx: Int, idx: Int): Int = {
            if (idx == array.length) minIdx
            else if (array(idx) < array(minIdx)) findMinIdx(idx, idx+1)
            else findMinIdx(minIdx, idx+1)
        }
        // swap関数
        def swap(x: Int, y: Int) {
            val tmp = array(x); array(x) = array(y); array(y) = tmp;
        }

        for(i <- 0 until array.length) {
            swap(i, findMinIdx(i, i+1))
        }
    }

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

}