Kotlinでバブルソートを実装する

最近クイックソートを何も見ずに実装できなくてとても悔しかったので、アルゴリズムの勉強をしています。今回はまずバブルソートを書いてみます。

前提

• 配列の要素が空白区切りで入力される
  例: 1 2 3 4 5

• 昇順にソートする

• 要素の数nの最大は100

実装

fun main(args: Array<String>){

    val array = readLine()!!.split(" ").map{it.toInt()}.toTypedArray()

    for( i in 0 until array.size - 1){
        for( j in array.size - 1 downTo i + 1){
            if(array[j] < array[j - 1]){
                val temp = array[j]
                array[j] = array[j-1]
                array[j-1] = temp
            }
        }
    }

    println(array.joinToString( ",", "[", "]"))
}

計算量

今回のケースでは昇順にソートすることが目的なので、計算量が最大になるのは、初期値で与えられる配列の要素が降順に並んでいるときです。 例えば、[5, 4, 3, 2, 1]と並んでいる場合は、比較を行う度に必ず要素の入れ替えが発生します。この例では、1の入れ替えを4回, 2の入れ替えを3回, 3の入れ替えを2回, 4の入れ替えを1回行うので、合計で4+3+2+1=10回の入れ替え操作が発生します。 仮にサイズnの配列の初期値が降順に並んでいた場合、入れ替え操作は(n -1) + (n - 2) + (n - 3) + ...+ 3 + 2 + 1 = n(n-1)/2回発生することになります。 計算量では最大の次数だけを考えるので、バブルソートの計算量はO(n²)となります。