[Scala][基礎アルゴリズム] 交換ソート（１） 単純交換法（バブルソート）

バブルソートと呼ばれる単純交換法。
「隣り合ったキー同士を順次比較していって、大小の順序が逆転しているなら位置を入れ替えるという操作を繰り返す方法である。」（『データ構造(P124)』）

Wikipediaの説明：バブルソート

・最悪の場合の計算量はO(n^2)

object BubbleSort {

    def sort(array: Array[Int]) = {
        // 配列の最後の要素を、適切な位置まで交換を繰り返して浮上させる
        // stop より前は整列済みとみなす
        def bubble(stop: Int) {
            if (stop < array.length) {
                var sw = array.length - 1
                for (i <- array.length - 1 to stop by -1) {
                    if (array(i) < array(i-1)) {
                        swap(i, i-1)
                        sw = i // 最後に交換が起こった位置
                    }
                }
                println(sw + "番目の要素より前は整列済み. " + array.toString)
                bubble(sw + 1)
            }
        }

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

        bubble(1)
    }

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

// 実行結果

-*- BubbleSortTest -*-
ソート前: Array(2, 9, 3, 5, 8, 7, 4, 1, 6)
1番目の要素より前は整列済み. Array(1, 2, 9, 3, 5, 8, 7, 4, 6)
3番目の要素より前は整列済み. Array(1, 2, 3, 9, 4, 5, 8, 7, 6)
4番目の要素より前は整列済み. Array(1, 2, 3, 4, 9, 5, 6, 8, 7)
5番目の要素より前は整列済み. Array(1, 2, 3, 4, 5, 9, 6, 7, 8)
6番目の要素より前は整列済み. Array(1, 2, 3, 4, 5, 6, 9, 7, 8)
7番目の要素より前は整列済み. Array(1, 2, 3, 4, 5, 6, 7, 9, 8)
8番目の要素より前は整列済み. Array(1, 2, 3, 4, 5, 6, 7, 8, 9)
ソート後: Array(1, 2, 3, 4, 5, 6, 7, 8, 9)