Quick Sort (퀵 정렬)
Quick Sort는 분할 정복(divide and conquer) 전략으로 동작하는 비교 정렬 알고리즘입니다. 평균 시간 복잡도 로 실무에서 가장 널리 쓰이는 정렬 알고리즘 중 하나이며, 많은 표준 라이브러리가 Quick Sort 또는 그 변형(Introsort, Timsort)을 기본 구현으로 채택합니다.
이 글에서는 Quick Sort의 동작 원리를 단계별로 살펴보고, 직접 인터랙션 가능한 시각화로 확인하며, 주의해야 할 케이스를 짚어봅니다. 동시에 이 페이지는 Backend Notes 블로그의 모든 MDX 문법을 한눈에 볼 수 있는 스타일 가이드이기도 합니다.
개요
Quick Sort의 핵심 아이디어는 간단합니다:
- 배열에서 피벗(pivot) 하나를 고릅니다
- 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할합니다
- 좌우 각각에 대해 재귀적으로 같은 과정을 반복합니다
이 과정을 그림으로 표현하면 다음과 같습니다:
데이터베이스 인덱스도 유사한 분할 정복 사고방식을 활용합니다. 인덱스 탐색은 B-TreeB-Tree를 통해 매 단계 탐색 범위를 절반 가까이로 줄이는 방식인데, Quick Sort의 "피벗으로 분할" 아이디어와 직관적으로 닮아있습니다.
알고리즘 단계
Lomuto 파티션 방식을 기준으로 동작을 정리하면:
- 배열의 마지막 원소를 피벗으로 선택
i = lo - 1로 파티션 경계 초기화j를lo부터hi - 1까지 순회하며:arr[j] <= pivot이면i를 1 증가시키고arr[i]와arr[j]교환
- 마지막으로
arr[i+1]와arr[hi](피벗) 교환 - 피벗의 최종 위치
i+1을 기준으로 좌우 서브 배열에 재귀 호출
의사 코드
def quick_sort(arr, lo, hi):
if lo < hi:
pivot_index = partition(arr, lo, hi)
quick_sort(arr, lo, pivot_index - 1)
quick_sort(arr, pivot_index + 1, hi)
def partition(arr, lo, hi):
pivot = arr[hi]
i = lo - 1
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[hi] = arr[hi], arr[i + 1]
return i + 1Kotlin 구현
실무에서 자주 쓰이는 Kotlin으로는 다음과 같이 작성할 수 있습니다:
fun <T : Comparable<T>> quickSort(arr: MutableList<T>, lo: Int = 0, hi: Int = arr.lastIndex) {
if (lo >= hi) return
val pivotIndex = partition(arr, lo, hi)
quickSort(arr, lo, pivotIndex - 1)
quickSort(arr, pivotIndex + 1, hi)
}
private fun <T : Comparable<T>> partition(arr: MutableList<T>, lo: Int, hi: Int): Int {
val pivot = arr[hi]
var i = lo - 1
for (j in lo until hi) {
if (arr[j] <= pivot) {
i++
val tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp
}
}
val tmp = arr[i + 1]; arr[i + 1] = arr[hi]; arr[hi] = tmp
return i + 1
}
fun main() {
val nums = mutableListOf(38, 27, 43, 3, 9, 82, 10)
quickSort(nums)
println(nums) // [3, 9, 10, 27, 38, 43, 82]
}Kotlin의 <T : Comparable<T>> 제약은 Java의 <T extends Comparable<T>> 와 동일합니다. 타입 파라미터를 통해 모든 비교 가능한 타입에 대해 재사용할 수 있습니다.
TypeScript 구현
export function quickSort<T>(arr: T[], compare: (a: T, b: T) => number = defaultCompare): T[] {
const out = arr.slice()
sort(out, 0, out.length - 1, compare)
return out
}
function sort<T>(arr: T[], lo: number, hi: number, compare: (a: T, b: T) => number): void {
if (lo >= hi) return
const p = partition(arr, lo, hi, compare)
sort(arr, lo, p - 1, compare)
sort(arr, p + 1, hi, compare)
}
function partition<T>(arr: T[], lo: number, hi: number, compare: (a: T, b: T) => number): number {
const pivot = arr[hi]
let i = lo - 1
for (let j = lo; j < hi; j++) {
if (compare(arr[j], pivot) <= 0) {
i++
;[arr[i], arr[j]] = [arr[j], arr[i]]
}
}
;[arr[i + 1], arr[hi]] = [arr[hi], arr[i + 1]]
return i + 1
}
function defaultCompare<T>(a: T, b: T): number {
return a < b ? -1 : a > b ? 1 : 0
}시각화
말로 설명하는 것보다 직접 움직이는 배열을 보는 편이 이해하기 쉽습니다. 아래 컴포넌트로 피벗 선택·비교·교환·확정의 단계별 흐름을 확인하세요. Play 버튼으로 자동 재생도 가능합니다.
Quick Sort 분할 과정
피벗을 기준으로 배열이 분할되는 과정을 단계별로 확인하세요.
피벗은 amber(주황), 비교 중인 원소는 blue(파랑), 확정된 위치는 emerald(초록)로 표시됩니다. Step 설명에서 매 동작의 근거를 확인할 수 있습니다.
시간 복잡도
| 케이스 | 시간 복잡도 | 설명 |
|---|---|---|
| 최선 | 피벗이 항상 배열을 균등하게 분할 | |
| 평균 | 랜덤 피벗 선택 시의 기대값 | |
| 최악 | 이미 정렬된 배열 + 끝 원소를 피벗으로 선택 |
공간 복잡도는 재귀 스택의 깊이에 비례해 이며, 최악의 경우 까지 증가할 수 있습니다.
SQL에서의 정렬
데이터베이스는 ORDER BY 절을 처리할 때 내부적으로 정렬 알고리즘을 사용합니다. PostgreSQL의 경우 기본적으로 외부 병합 정렬(external merge sort)을 사용하지만, 데이터 크기가 work_mem 안에 들어오면 quicksort로 전환됩니다.
-- 인덱스가 없는 컬럼을 정렬 → Quick Sort 또는 Merge Sort 사용
EXPLAIN ANALYZE
SELECT id, name, created_at
FROM users
ORDER BY created_at DESC
LIMIT 100;
-- 실행 계획에 "Sort Method: quicksort" 가 나타나면 메모리 내 정렬
-- "external merge" 가 나타나면 디스크 기반 정렬로 전환된 것주의사항
Quick Sort를 쓸 때 자주 마주치는 함정들입니다.