• 데이터 중 임의 대상, Pivot을 선택하여 Pivot을 기준으로 정렬하는 방식
• 평균적으로 매우 빠른 성능을 보이지만, 최악의 경우엔 성능이 저하되어 시간복잡도가 올라갈 수 있다
  • 최악의 경우는 배열이 이미 정렬되어 있을 때, Pivot을 최소나 최대로 선택했을 때인데, 이렇게 되면 분할이 매우 불균형적으로 이루어져 재귀 깊이가 증가하게 되기 때문
• 시간 복잡도 : O(nlogn), 공간 복잡도 : O(logn)

fun main() {
    val arr = intArrayOf(3, 2, 5, 1, 4)
    quickSort(arr, 0, arr.size - 1)
    println(arr.contentToString())
}

// 배열을 퀵 정렬 방식으로 정렬하는 함수
fun quickSort(arr: IntArray, start: Int, end: Int) {
    if (start < end) {
        val pivot = partition(arr, start, end)
        quickSort(arr, start, pivot - 1) // 피벗 왼쪽 부분 배열 정렬
        quickSort(arr, pivot + 1, end) // 피벗 오른쪽 부분 배열 정렬
    }
}

// 파티션 함수: 배열을 피벗을 기준으로 두 부분으로 나눔
fun partition(arr: IntArray, start: Int, end: Int): Int {
    val pivot = arr[end] // 피벗을 배열의 마지막 요소로 지정
    var i = start - 1 // 피벗보다 작은 요소들의 인덱스를 추적

    for (j in start until end) {
        // 현재 요소가 피벗보다 작으면
        if (arr[j] < pivot) {
            i++ // 'i'를 증가시키고
            // arr[i]와 arr[j]를 스왑
            arr[i] = arr[j].also { arr[j] = arr[i] }
        }
    }
    // 피벗을 중간으로 이동
    arr[i + 1] = arr[end].also { arr[end] = arr[i + 1] }
    return i + 1 // 새로운 피벗의 위치 반환
}