코틀린 퀵 소트(퀵 정렬) 소스코드

학부생 때나 하던 건데 오랜만에 갑자기 퀵 소트 구현이나 해볼까해서

위키피디아에 있는 퀵 소트 수도 코드를 보면서 코틀린으로 그대로 옮겨봤습니다

 

fun main() {
    val array = intArrayOf(3,7,8,5,2,1,9,5,4)
    array.quickSort()

    println(array.contentToString()) // [1, 2, 3, 4, 5, 5, 7, 8, 9]
}

fun IntArray.quickSort(start: Int = 0, end: Int = this.size - 1) {
    if (start >= 0 && end >= 0 && start < end) {
        val pivotIndex = this.partition(start, end)

        this.quickSort(start, pivotIndex)
        this.quickSort(pivotIndex + 1, end)
    }
}

/**
 * 가장 오른쪽 원소를 피벗으로 삼아서 작은 원소는 피벗 왼쪽으로, 큰 원소는 피벗 오른쪽으로 몰아놓음
 * ex) 피벗보다 작은 원소가 3개, 큰 원소가 6개라면
 * [0] ~ [2]: 피벗보다 작은 원소들
 * [3]: 피벗
 * [4] ~ [9]: 피벗보다 큰 원소들
 * 이렇게 이동시킴
 */
private fun IntArray.partition(start: Int, end: Int): Int {
    val pivot = this[((end - start) / 2) + start] // start ~ end 사이 가운데 인덱스를 피벗으로

    var left = start - 1
    var right = end + 1

    while (true) {
        do {
            left++
        } while (this[left] < pivot)

        do {
            right--
        } while (this[right] > pivot)

        if (left >= right) {
            return right
        }

        swap(left, right)
    }
}

/**
 * i와 j번째 원소를 스왑
 */
private fun IntArray.swap(i: Int, j: Int) {
    this[i] = this[j].also { this[j] = this[i] }
}