이번 포스팅은 정렬 알고리즘 중 빠르다고 알려진 Quick Sort(퀵 정렬) 에 대해 3가지 주제를 중심으로 알아보려 합니다.
- 퀵 정렬의 기본 원리
- 퀵 정렬의 시간 복잡도
- 피벗 선택 방법의 차이
퀵 정렬의 기본 원리
Quick Sort(퀵 정렬)은 분할 정복(Divide and Conquer) 알고리즘을 기반으로하는 알고리즘입니다.
퀵 정렬의 기본 동작을 알아보겠습니다.
- 피벗 선택: 배열에서 요소 하나를 선택해서 피벗으로 정합니다.
- 분할: 정한 피벗을 기준으로 배열을 두 부분으로 나눕니다.
이때 피벗보다 작은 요소는 피벗의 왼쪽으로, 피벗보다 큰 요소는 피벗의 오른쪽으로 위치합니다. - 재귀적 정렬: 분할된 두 부분에 대해 재귀적으로 퀵 정렬을 수행합니다.
퀵 정렬의 시간 복잡도
퀵 정렬의 시간 복잡도는 피벗을 어떻게 선택하고, 배열을 어떻게 분할하느냐에 따라 달라질 수 있습니다.
분할과 정렬 과정에서 발생하는 연산의 양을 봅시다.
먼저, 한 번의 분할 과정에서 피벗과 배열의 모든 요소를 비교합니다. 이때 배열의 길이인 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) 의 시간 복잡도가 됩니다.
피벗 선택 방법의 차이
퀵 정렬에선 피벗을 어떻게 선택하냐에 따라 배열을 분할할 때 효율이 달라집니다.
다음 세 가지 방법을 코틀린 코드로 비교해보겠습니다.
- 가장 왼쪽에 있는 요소를 피벗으로 선택
- 중간에 있는 요소를 피벗으로 선택
- 가장 오른쪽에 있는 요소를 피벗으로 선택
가장 왼쪽에 있는 요소를 피벗으로 선택한 경우
이미 정렬된 배열이 아니라면, 이 방법과 가장 오른쪽에 있는 요소를 선택하는 경우가 유사한 결과를 낼 수 있습니다.
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)
}
}