[Kotlin] Quick Sort(퀵 정렬) 알고리즘

 

위키피디아 - 퀵 정렬

이번 포스팅은 정렬 알고리즘 중 빠르다고 알려진 Quick Sort(퀵 정렬) 에 대해 3가지 주제를 중심으로 알아보려 합니다.

• 퀵 정렬의 기본 원리
• 퀵 정렬의 시간 복잡도
• 피벗 선택 방법의 차이

퀵 정렬의 기본 원리

Quick Sort(퀵 정렬)은 분할 정복(Divide and Conquer) 알고리즘을 기반으로하는 알고리즘입니다.

 

퀵 정렬의 기본 동작을 알아보겠습니다.

1. 피벗 선택: 배열에서 요소 하나를 선택해서 피벗으로 정합니다.
2. 분할: 정한 피벗을 기준으로 배열을 두 부분으로 나눕니다.
   이때 피벗보다 작은 요소는 피벗의 왼쪽으로, 피벗보다 큰 요소는 피벗의 오른쪽으로 위치합니다.
3. 재귀적 정렬: 분할된 두 부분에 대해 재귀적으로 퀵 정렬을 수행합니다.

퀵 정렬의 시간 복잡도

퀵 정렬의 시간 복잡도는 피벗을 어떻게 선택하고, 배열을 어떻게 분할하느냐에 따라 달라질 수 있습니다.

분할과 정렬 과정에서 발생하는 연산의 양을 봅시다.

 

먼저, 한 번의 분할 과정에서 피벗과 배열의 모든 요소를 비교합니다. 이때 배열의 길이인 n 에 비례하는 연산을 수행하므로 O(n) 의 시간 복잡도를 가집니다.

 

그리고나서 전체 퀵 정렬을 봅시다.

퀵 정렬은 배열을 계속해서 두 부분으로 나누면서 정렬을 수행합니다.

이 과정이 재귀적으로 수행되며, 각 재귀 단계에서 균등에 가깝게 분할되면 재귀 호출의 깊이가 어떻게 될까요?

 

여기서 분할 정복 알고리즘을 조금 살펴 봐야 합니다.

• 매 분할 단계마다 배열을 두 부분으로 나눕니다.
• 각 분할마다 균등하게 분할된다면 분할되는 배열의 크기는 매번 이전 배열의 절반으로 줄어듭니다.
• 배열이 더 이상 분할할 수 없는 크기(크기가 1인 배열) 가 될 때 까지 반복됩니다.
• 배열을 절반씩 나누는 단계들은 총 log n 번 반복됩니다. => 따라서 재귀 호출의 깊이는 log n 에 비례합니다.

재귀 호출의 깊이가 log n 이고, 각 깊이에서 n 번의 비교 작업을 하므로 평균적으로 O(n log n) 의 시간 복잡도를 가집니다.

하지만, 최악의 경우엔 O(n^2) 까지 늘어날 수 있습니다.

 

왜 그럴까요?

최선의 경우

재귀 호출의 깊이는 배열이 분할된 깊이에 비례합니다. 따라서 최적의 경우 깊이는 log n 이 됩니다.

최초로 배열을 분할하면 배열의 모든 요소를 피벗과 비교하게 됩니다. 따라서 n 번의 연산을 하게되죠.

이로써 평균적으로 O(n log n) 의 시간 복잡도가 됩니다.

 

최악의 경우

만약 이미 정렬된 배열을 퀵 정렬한다면 어떻게 될까요?

오름차순으로 정렬되거나 내림차순으로 정렬된 경우를 생각해보면, 피벗이 가장 왼쪽이거나 가장 오른쪽일 때 분할되는 경우를 봅시다.

분할된 두 부분 중 한 부분의 요소 개수는 n - 1 개가 됩니다.

다시 말해, 분할을 할 때마다 매우 불균등하게 분할됩니다.

 

즉, 재귀 호출의 깊이는 n 이 되고, 각 깊이에서 피벗에 대한 모든 요소와 비교 작업에 의해 n 번의 연산이 필요하죠.

이 때문에 최악의 경우 O(n^2) 의 시간 복잡도가 됩니다.

 

피벗 선택 방법의 차이

퀵 정렬에선 피벗을 어떻게 선택하냐에 따라 배열을 분할할 때 효율이 달라집니다.

다음 세 가지 방법을 코틀린 코드로 비교해보겠습니다.

1. 가장 왼쪽에 있는 요소를 피벗으로 선택
2. 중간에 있는 요소를 피벗으로 선택
3. 가장 오른쪽에 있는 요소를 피벗으로 선택

가장 왼쪽에 있는 요소를 피벗으로 선택한 경우

이미 정렬된 배열이 아니라면, 이 방법과 가장 오른쪽에 있는 요소를 선택하는 경우가 유사한 결과를 낼 수 있습니다.

fun quickSort(arr: MutableList<String>, left: Int, right: Int) {
    if (left < right) {
        val pivotIndex = partition(arr, left, right, left) // 피벗 인덱스 계산
        quickSort(arr, left, pivotIndex - 1) // 왼쪽부터 피벗 직전까지 퀵 정렬
        quickSort(arr, pivotIndex + 1, right) // 피벗 다음부터 오른쪽까지 퀵 정렬
    }
}

fun partition(arr: MutableList<String>, left: Int, right: Int, pivotIndex: Int): Int {
    val pivot = arr[pivotIndex] // 피벗 선택
    var i = left // 현재까지 피벗보다 작은 요소의 마지막 인덱스

    // 피벗을 기준으로 요소들을 분할
    for (j in left until right) {
        if (arr[j] <= pivot) { // 피벗보다 작거나 같은지 확인
            swap(arr, i, j) // 작거나 같으면 스왑
            i++
        }
    } // 루프를 마치면 i는 피벗보다 작은 마지막 요소의 인덱스를 가리키게 됨

    // 피벗을 올바른 위치로 이동 => 피벗은 정확히 "작은 요소와 큰 요소를 나누는 경계"에 위치
    swap(arr, i, right)
    return i // 피벗의 최종 위치 반환
}

fun swap(arr: MutableList<String>, i: Int, j: Int) {
    val temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}

 

중간에 있는 요소를 피벗으로 선택한 경우

중간 요소를 피벗으로 선택한다면 배열이 균등하게 분할될 가능성이 높아집니다.

분할하는 함수는 위와 동일하므로 생략합니다.

fun quickSort(arr: MutableList<String>, left: Int, right: Int) {
    if (left < right) {
        val middle = left + (right - left) / 2
        val pivotIndex = partition(arr, left, right, middle)
        quickSort(arr, left, pivotIndex - 1)
        quickSort(arr, pivotIndex + 1, right)
    }
}

가장 오른쪽에 있는 요소를 피벗으로 선택한 경우

왼쪽 끝에 있는 요소를 피벗으로 선택한 경우와 유사한 결과가 나올 수 있습니다.

하지만, 배열에 있는 데이터의 패턴에 따라 더 유리할 수도 있죠.

fun quickSort(arr: MutableList<String>, left: Int, right: Int) {
    if (left < right) {
        val pivotIndex = partition(arr, left, right, right)
        quickSort(arr, left, pivotIndex - 1)
        quickSort(arr, pivotIndex + 1, right)
    }
}