퀵 정렬이란 병합 정렬과 같이 분할 정복 (Divide and Conquer) 알고리즘에 속하며, 재귀를 사용한다. 하지만 병합 정렬과는 다른 방식으로 동작한다
핵심 원리
- 피벗(Pivot) 선택: 배열에서 기준이 될 원소를 선택한다
- 분할(Partition): 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 이동한다
- 재귀(Recursion): 피벗을 기준으로 나뉜 두 영역을 각각 퀵 정렬한다
병합 정렬과의 차이점
- 병합 정렬: 무조건 반으로 나눈 후 → 정렬하며 병합
- 퀵 정렬: 피벗 기준으로 정렬하며 나눔 → 재귀 호출
동작 과정 상세 분석
배열 [5, 3, 7, 2, 6, 4, 9, 1, 8]을 오름차순으로 정렬하는 과정을 단계별로 살펴보자
═══════════════════════════════════════════════════
퀵 정렬의 핵심 변수들
═══════════════════════════════════════════════════
pivot (피벗)
└─ 기준이 되는 값 (보통 맨 왼쪽 원소 선택)
left
└─ 정렬 범위의 시작 인덱스
right
└─ 정렬 범위의 끝 인덱스
leftStartIndex
└─ 왼쪽에서 오른쪽으로 이동하며 피벗보다 큰 값 찾기
rightStartIndex
└─ 오른쪽에서 왼쪽으로 이동하며 피벗보다 작은 값 찾기
1단계: 초기 설정
═══════════════════════════════════════════════════
배열: [5, 3, 7, 2, 6, 4, 9, 1, 8]
═══════════════════════════════════════════════════
pivot = 5 (가장 왼쪽 원소)
↓
[5, 3, 7, 2, 6, 4, 9, 1, 8]
↑ ↑ ↑
left L R
leftStartIndex rightStartIndex
left = 0 (인덱스)
right = 8 (인덱스)
leftStartIndex = 1 (피벗 다음)
rightStartIndex = 8 (배열 끝)
2단계: 첫 번째 교환
═══════════════════════════════════════════════════
Step 1: leftStartIndex 이동 (피벗보다 큰 값 찾기)
═══════════════════════════════════════════════════
[5, 3, 7, 2, 6, 4, 9, 1, 8]
↑ ↑
3 7 ← 7 > 5 (피벗) → 멈춤
L
leftStartIndex = 2 (7의 위치)
═══════════════════════════════════════════════════
Step 2: rightStartIndex 이동 (피벗보다 작은 값 찾기)
═══════════════════════════════════════════════════
[5, 3, 7, 2, 6, 4, 9, 1, 8]
↑ ↑
1 8
R
1 < 5 (피벗) → 멈춤
rightStartIndex = 7 (1의 위치)
═══════════════════════════════════════════════════
Step 3: 교환
═══════════════════════════════════════════════════
leftStartIndex(2) < rightStartIndex(7)
→ 서로 지나치지 않았으므로 교환
[5, 3, 7, 2, 6, 4, 9, 1, 8]
↕ ↕
[5, 3, 1, 2, 6, 4, 9, 7, 8]
3단계: 두 번째 교환
═══════════════════════════════════════════════════
Step 1: leftStartIndex 계속 이동 (피벗보다 큰 값 찾기)
═══════════════════════════════════════════════════
[5, 3, 1, 2, 6, 4, 9, 7, 8]
↑ ↑
2 6 ← 6 > 5 (피벗) → 멈춤
L
leftStartIndex = 4
═══════════════════════════════════════════════════
Step 2: rightStartIndex 계속 이동 (피벗보다 작은 값 찾기)
═══════════════════════════════════════════════════
[5, 3, 1, 2, 6, 4, 9, 7, 8]
↑ ↑
4 9
R
4 < 5 (피벗) → 멈춤
rightStartIndex = 5
═══════════════════════════════════════════════════
Step 3: 교환
═══════════════════════════════════════════════════
leftStartIndex(4) < rightStartIndex(5)
→ 교환
[5, 3, 1, 2, 6, 4, 9, 7, 8]
↕ ↕
[5, 3, 1, 2, 4, 6, 9, 7, 8]
4단계: 포인터가 교차
═══════════════════════════════════════════════════
Step 1: leftStartIndex 계속 이동 (피벗보다 큰 값 찾기)
═══════════════════════════════════════════════════
[5, 3, 1, 2, 4, 6, 9, 7, 8]
↑
6 > 5 → 멈춤!
L
leftStartIndex = 5
═══════════════════════════════════════════════════
Step 2: rightStartIndex 계속 이동 (피벗보다 작은 값 찾기)
═══════════════════════════════════════════════════
[5, 3, 1, 2, 4, 6, 9, 7, 8]
↑
4 < 5 → 멈춤!
R
rightStartIndex = 4
═══════════════════════════════════════════════════
Step 3: 포인터 교차 확인
═══════════════════════════════════════════════════
leftStartIndex(5) > rightStartIndex(4)
→ 서로 지나쳤다
→ 교환하지 않고 while문 종료
5단계: 피벗과 교환 (핵심)
═══════════════════════════════════════════════════
피벗과 rightStartIndex 교환
═══════════════════════════════════════════════════
[5, 3, 1, 2, 4, 6, 9, 7, 8]
↑ ↑
pivot rightStartIndex
교환
[4, 3, 1, 2, 5, 6, 9, 7, 8]
↑
피벗 정렬 완료
═══════════════════════════════════════════════════
결과 분석
═══════════════════════════════════════════════════
[4, 3, 1, 2] | [5] | [6, 9, 7, 8]
└─────┬────┘ ↑ └─────┬────┘
5보다 피벗 5보다
작은 값 정렬됨 큰 값
5는 정렬 완료
왼쪽: 모두 5보다 작음
오른쪽: 모두 5보다 큼
6단계: 재귀 호출
═══════════════════════════════════════════════════
왼쪽 영역 재귀 호출
═══════════════════════════════════════════════════
QuickSort([4, 3, 1, 2], 0, 3)
피벗 = 4
분할 후: [2, 3, 1, 4]
재귀...
최종: [1, 2, 3, 4]
═══════════════════════════════════════════════════
오른쪽 영역 재귀 호출
═══════════════════════════════════════════════════
QuickSort([6, 9, 7, 8], 5, 8)
피벗 = 6
분할 후: [6, 9, 7, 8]
재귀...
최종: [6, 7, 8, 9]
═══════════════════════════════════════════════════
최종 결과
═══════════════════════════════════════════════════
[1, 2, 3, 4, 5, 6, 7, 8, 9]
재귀 호출 트리 시각화
[5,3,7,2,6,4,9,1,8]
pivot=5
↓
[4,3,1,2,5,6,9,7,8]
↑
정렬됨
│
┌────────────┴────────────┐
↓ ↓
[4,3,1,2] [6,9,7,8]
pivot=4 pivot=6
↓ ↓
[2,3,1,4] [6,9,7,8]
↑ ↑
정렬됨 정렬됨
│ │
┌────┴────┐ ┌────┴────┐
↓ ↓ ↓ ↓
[2,3,1] [4] [6] [9,7,8]
pivot=2 정렬됨 정렬됨 pivot=9
↓ ↓
[1,2,3] [7,8,9]
↑ ↑
정렬됨 정렬됨
최종: [1,2,3,4,5,6,7,8,9]
분할(Partition) 과정 상세
1. 피벗 선택 (보통 첫 번째 원소)
[5, 3, 7, 2, 6, 4, 9, 1, 8]
↑
pivot
2. 포인터 초기화
L: leftStartIndex (피벗 다음)
R: rightStartIndex (배열 끝)
3. 반복 (L과 R이 교차할 때까지)
a. L을 오른쪽으로: pivot보다 큰 값 찾기
b. R을 왼쪽으로: pivot보다 작은 값 찾기
c. L < R이면 교환
d. L > R이면 종료
4. 피벗과 R 교환
→ 피벗이 올바른 위치로
5. 피벗 인덱스 반환
Java 구현
public class QuickSort {
/**
* 퀵 정렬 메인 함수
* @param arr 정렬할 배열
* @param left 정렬 범위의 시작 인덱스
* @param right 정렬 범위의 끝 인덱스
*/
public static void quickSort(int[] arr, int left, int right) {
// 기저 조건: left가 right보다 작거나 같을 때만 진행
if (left <= right) {
// 분할: 피벗을 기준으로 정렬하고 피벗의 최종 위치 반환
int pivot = divide(arr, left, right);
// 왼쪽 영역 재귀 정렬 (피벗 제외)
quickSort(arr, left, pivot - 1);
// 오른쪽 영역 재귀 정렬 (피벗 제외)
quickSort(arr, pivot + 1, right);
}
}
/**
* 분할 함수: 피벗을 기준으로 배열을 분할하고 피벗을 정렬
* @param arr 배열
* @param left 범위 시작
* @param right 범위 끝
* @return 정렬된 피벗의 인덱스
*/
private static int divide(int[] arr, int left, int right) {
// 피벗 선택 (가장 왼쪽 원소)
int pivot = arr[left];
// 왼쪽에서 시작하는 포인터 (피벗 다음부터)
int leftStartIndex = left + 1;
// 오른쪽에서 시작하는 포인터
int rightStartIndex = right;
// 두 포인터가 교차할 때까지 반복
while (leftStartIndex <= rightStartIndex) {
// leftStartIndex: 피벗보다 큰 값을 찾을 때까지 오른쪽으로 이동
while (leftStartIndex <= right && pivot >= arr[leftStartIndex]) {
leftStartIndex++;
}
// rightStartIndex: 피벗보다 작은 값을 찾을 때까지 왼쪽으로 이동
while (rightStartIndex >= (left + 1) && pivot <= arr[rightStartIndex]) {
rightStartIndex--;
}
// 두 포인터가 아직 교차하지 않았다면 값 교환
if (leftStartIndex < rightStartIndex) {
swap(arr, leftStartIndex, rightStartIndex);
}
}
// 피벗과 rightStartIndex 위치의 값 교환
// → 피벗이 올바른 위치로 이동
swap(arr, left, rightStartIndex);
// 정렬된 피벗의 인덱스 반환
return rightStartIndex;
}
/**
* 배열의 두 원소를 교환하는 헬퍼 함수
* @param arr 배열
* @param index1 첫 번째 인덱스
* @param index2 두 번째 인덱스
*/
private static void swap(int[] arr, int index1, int index2) {
int temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
// 배열 출력 메서드
public static void printArray(int[] arr) {
System.out.print("[");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]);
if (i < arr.length - 1) {
System.out.print(", ");
}
}
System.out.println("]");
}
// 테스트 메인 메서드
public static void main(String[] args) {
System.out.println("=== 기본 퀵 정렬 ===");
int[] arr = {5, 3, 7, 2, 6, 4, 9, 1, 8};
System.out.println("정렬 전:");
printArray(arr);
quickSort(arr, 0, arr.length - 1);
System.out.println("정렬 후:");
printArray(arr);
}
}
/*
실행 결과
=== 기본 퀵 정렬 ===
정렬 전:
[5, 3, 7, 2, 6, 4, 9, 1, 8]
정렬 후:
[1, 2, 3, 4, 5, 6, 7, 8, 9]
*/
단계별 퀵 정렬
→ quickSort 호출: left=0, right=8
범위: [5, 3, 7, 2, 6, 4, 9, 1, 8]
pivot = 5
분할 시작...
교환: arr[2](7) ↔ arr[7](1)
교환: arr[4](6) ↔ arr[5](4)
피벗 교환: arr[0](5) ↔ arr[4](4)
→ 피벗 4가 인덱스 4에 정렬됨
결과: [4, 3, 1, 2, 5, 6, 9, 7, 8]
→ quickSort 호출: left=0, right=3
범위: [4, 3, 1, 2]
pivot = 4
분할 시작...
교환: arr[1](3) ↔ arr[3](2)
피벗 교환: arr[0](4) ↔ arr[3](2)
→ 피벗 2이(가) 인덱스 3에 정렬됨
결과: [2, 3, 1, 4]
→ quickSort 호출: left=0, right=2
범위: [2, 3, 1]
pivot = 2
분할 시작...
교환: arr[1](3) ↔ arr[2](1)
피벗 교환: arr[0](2) ↔ arr[2](1)
→ 피벗 1이(가) 인덱스 2에 정렬됨
결과: [1, 3, 2]
→ quickSort 호출: left=0, right=1
범위: [1, 3]
pivot = 1
분할 시작...
피벗 교환: arr[0](1) ↔ arr[0](1)
→ 피벗 1이(가) 인덱스 0에 정렬됨
결과: [1, 3]
→ quickSort 호출: left=0, right=-1
기저 조건 도달 (정렬 불필요)
→ quickSort 호출: left=1, right=1
기저 조건 도달 (정렬 불필요)
→ quickSort 호출: left=3, right=2
기저 조건 도달 (정렬 불필요)
→ quickSort 호출: left=4, right=3
기저 조건 도달 (정렬 불필요)
→ quickSort 호출: left=5, right=8
범위: [6, 9, 7, 8]
pivot = 6
분할 시작...
피벗 교환: arr[5](6) ↔ arr[5](6)
→ 피벗 6이(가) 인덱스 5에 정렬됨
결과: [6, 9, 7, 8]
→ quickSort 호출: left=5, right=4
기저 조건 도달 (정렬 불필요)
→ quickSort 호출: left=6, right=8
범위: [9, 7, 8]
pivot = 9
분할 시작...
교환: arr[6](9) ↔ arr[8](8)
피벗 교환: arr[6](8) ↔ arr[8](9)
→ 피벗 9이(가) 인덱스 8에 정렬됨
결과: [8, 7, 9]
→ quickSort 호출: left=6, right=7
범위: [8, 7]
pivot = 8
분할 시작...
피벗 교환: arr[6](8) ↔ arr[7](7)
→ 피벗 7이(가) 인덱스 7에 정렬됨
결과: [7, 8]
→ quickSort 호출: left=6, right=6
기저 조건 도달 (정렬 불필요)
→ quickSort 호출: left=8, right=7
기저 조건 도달 (정렬 불필요)
→ quickSort 호출: left=9, right=8
기저 조건 도달 (정렬 불필요)
시간 복잡도
평균 경우 (Best & Average Case)
═══════════════════════════════════════════════════
피벗이 배열을 균등하게 분할하는 경우
═══════════════════════════════════════════════════
레벨 0: [........] (n개)
피벗이 중간
└──┬──┘
↓
레벨 1: [....] [....] (n/2개씩, 2그룹)
└─┬─┘ └─┬─┘
↓ ↓
레벨 2: [..] [..] [..] [..] (n/4개씩, 4그룹)
↓ ↓ ↓ ↓
레벨 3: [.] [.] [.] [.] ... (1개씩, n그룹)
총 레벨 수: log₂n
각 레벨에서의 비교: n번
전체 비교 횟수: n × log₂n
시간 복잡도: Θ(n log n)
최악의 경우 (Worst Case)
═══════════════════════════════════════════════════
피벗이 항상 최솟값 또는 최댓값인 경우
═══════════════════════════════════════════════════
예: 이미 정렬된 배열 [1, 2, 3, 4, 5]
(피벗을 첫 번째 원소로 선택 시)
레벨 0: [1, 2, 3, 4, 5] (5개, 4번 비교)
↓
[] [2, 3, 4, 5]
레벨 1: [2, 3, 4, 5] (4개, 3번 비교)
↓
[] [3, 4, 5]
레벨 2: [3, 4, 5] (3개, 2번 비교)
↓
[] [4, 5]
레벨 3: [4, 5] (2개, 1번 비교)
↓
[] [5]
레벨 4: [5] (1개)
총 비교 횟수: 4 + 3 + 2 + 1 = 10 = n(n-1)/2
시간 복잡도: O(n²)
공간 복잡도
- 평균: O(log n) – 재귀 호출 스택
- 최악: O(n) – 완전히 불균형한 경우
장점
- 평균적으로 가장 빠름: 실전에서 O(n log n) 알고리즘 중 가장 빠른 성능을 자랑한다
- 적은 메모리 사용: O(log n)의 스택 공간만 필요하다 (제자리 정렬)
- 캐시 효율성: 연속된 메모리 접근으로 캐시 적중률이 높다
- 구현이 비교적 간단: 병합 정렬보다 구현이 쉽다
단점
- 최악의 경우 O(n²): 피벗 선택이 나쁠 경우 성능이 저하된다
- 불안정 정렬: 동일한 값의 순서가 바뀔 수가 있다
- 재귀 깊이: 최악의 경우 스택 오버플로우의 위험이 있다
- 예측 불가능: 입력 데이터에 따라 성능 차이가 크다