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(n²)になります。 平均の計算量としてはO(nlogn)です。 ピボットの選び方としては、配列の先頭の他にも、配列から3要素の中央値などの方法があります。2つの配列の分け方としては、どちらもできるだけ同じ要素数になるように配列を分けると、再帰呼び出しの数がより少なくなるので、中央値を基準として均等に分けようという考えです。