daisuzz.log

daisuzz.log

ソフトウェアエンジニアをしています。ソフトウェア開発に関することや読んだ本について書いているブログです。

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(n2)となります。