퀵 정렬

기준데이터(피벗)를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법

일반적인 상황에서 제일 많이 사용되는 정렬 알고리즘 중 하나.

 

평균적으로 O(NlogN)의 시간복잡도를 가지며, 최악의 경우  O(N^2)의 시간복잡도를 가진다.

 

fun main() {
    val array = intArrayOf(5,7,9,0,3,1,6,2,4,8)
    quickSort(array, 0, array.size - 1)
    // array.forEach { print("$it ") }
    print(array.contentToString())
}

fun quickSort(arr: IntArray, start: Int, end: Int) {
    if(start >= end) return

    val pivot = start
    var left = start + 1
    var right = end

    while(left <= right) {
        while(left <= end && arr[left] <= arr[pivot])
            left += 1
        while(right >= start && arr[right] >= arr[pivot])
            right -= 1

        if(left > right)
            swap(arr, pivot, right)
        else
            swap(arr, left, right)
    }

    quickSort(arr, start, right - 1)
    quickSort(arr, right + 1, end)
}

fun swap(arr: IntArray, i: Int, j: Int) {
    val temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}