퀵소트(Quick Sort)는 분할 정복 알고리즘 중 하나로, 비교 정렬에 사용되는 효율적인 방법입니다. 이 알고리즘은 평균적으로 O(n log n)의 시간복잡도를 가지며, 제자리 정렬 방식을 사용합니다. 이번 글에서는 코틀린을 사용하여 퀵소트 알고리즘을 구현하는 방법에 대해 알아보겠습니다.

퀵소트 알고리즘 개요

퀵소트 알고리즘은 다음과 같은 단계로 실행됩니다.

1. 분할: 배열에서 하나의 요소를 선택하고, 이를 피벗(pivot)으로 지정합니다.
2. 비교 및 교환: 피벗을 기준으로 배열을 분할하고, 작은 값은 왼쪽에, 큰 값은 오른쪽에 위치하도록 교환합니다.
3. 재귀: 왼쪽 배열과 오른쪽 배열에 대해 재귀적으로 위 과정을 반복합니다.

코틀린 코드 구현

이제 퀵소트 알고리즘을 코틀린으로 구현해보겠습니다.

fun quicksort(arr: IntArray, low: Int, high: Int) {
    if (low < high) {
        val pivot = partition(arr, low, high)
        quicksort(arr, low, pivot - 1)
        quicksort(arr, pivot + 1, high)
    }
}

fun partition(arr: IntArray, low: Int, high: Int): Int {
    val pivot = arr[high]
    var i = low - 1
    for (j in low until high) {
        if (arr[j] < pivot) {
            i++
            arr[i] = arr[j].also { arr[j] = arr[i] }
        }
    }
    arr[i + 1] = arr[high].also { arr[high] = arr[i + 1] }
    return i + 1
}

위의 코드는 배열을 입력받아 퀵소트 알고리즘을 수행하는 함수인 quicksort와 배열을 분할하는 함수인 partition으로 구성되어 있습니다. partition 함수는 호어 분할(Hoare Partition) 방식을 사용하여 피벗을 설정하고, 배열을 분할합니다.

실행 예제

다음은 주어진 배열을 퀵소트 알고리즘으로 정렬하는 예제 코드입니다.

fun main() {
    val arr = intArrayOf(5, 2, 9, 1, 5, 6)
    quicksort(arr, 0, arr.size - 1)
    println("정렬된 배열: ${arr.contentToString()}")
}

위 예제 코드를 실행하면, 다음과 같이 출력될 것입니다.

정렬된 배열: [1, 2, 5, 5, 6, 9]

퀵소트 알고리즘을 구현하고 실행하는 방법에 대해 알아보았습니다. 이를 통해 코틀린을 사용하여 효율적인 정렬 알고리즘을 구현하는 법에 대해 이해할 수 있었습니다.