daisuzz.log

daisuzz.log

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

Kotlinでクイックソートを実装する

前回バブルソートを実装したので、今回はクイックソートを実装してみます。 iikanji.hatenablog.jp

前提

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

  • 昇順にソートする

  • 要素の数nの最大は100

  • クイックソートで利用する、ピボットは配列の先頭の値とする

実装

fun quickSort(array: Array<Int>): Array<Int> {

    // 要素が1つしかない場合はソートを終了する 
    if (array.size == 1) return array

    // 先頭の要素をpivotとする
    val pivot = array[0]

    // 探索範囲左端
    var left = 0

    // 探索範囲右端
    var right = array.size - 1

    while (left < right) {

        // pivot以上の要素を探索
        while (array[left] < pivot) left++

        // pivot以下の要素を探索
        while (array[right] > pivot) right--

        // それぞれの位置を交換
        if (left <= right) {
            val temp = array[left]
            array[left] = array[right]
            array[right] = temp

            left++
            right--
        }
    }

    val leftList = mutableListOf<Int>()
    val rightList = mutableListOf<Int>()
    for (i in 0 until left) {
        leftList.add(array[i])
    }
    for (i in left until array.size) {
        rightList.add(array[i])
    }

    return quickSort(leftList.toTypedArray()) + quickSort(rightList.toTypedArray())
}

fun main() {

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

    val sortedArray = quickSort(array)

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

計算量

クイックソートは、ピボットの選び方によって、再帰呼び出しの回数が変わります。 最悪の場合は、要素数1の配列と、元の再帰関数に与えられた配列の要素数-1の配列に分けられると計算量はO(n2)になります。 平均の計算量としてはO(nlogn)です。 ピボットの選び方としては、配列の先頭の他にも、配列から3要素の中央値などの方法があります。2つの配列の分け方としては、どちらもできるだけ同じ要素数になるように配列を分けると、再帰呼び出しの数がより少なくなるので、中央値を基準として均等に分けようという考えです。