한국방송통신대 알고리즘 강의 4강 정리노트입니다.
📌 퀵 정렬 QuickSort
- 특정한 데이터를 기준(pivot)으로 배열을 2개의 부분배열로 분할
- 각 부분 배열에 대해 퀵 정렬을 순환적으로 적용
pivot pivot, 분할 원소
pivot은 분할 기준이 되는 특정 데이터입니다.
퀵 정렬은 pivot을 선택하여, pivot이 제자리를 잡도록 하여 정렬합니다.
- pivot보다 작은 값은 왼쪽
- pivot보다 큰 값은 오른쪽
왼쪽 부분 배열의 값 < pivot < 오른쪽 부분 배열의 값분할 과정
- 분할 과정의 시간 복잡도는 Θ(n)입니다.
- left는 왼쪽에서 오른쪽으로 이동하며, pivot보다 큰 값을 찾는다.
- right는 오른쪽에서 왼쪽으로 이동하며, pivot보다 작은 값을 찾는다.
- left와 right를 교환한다.
- left보다 right가 크다면, 분할을 멈추고 pivot과 right를 교환한다.
- pivot을 기준으로 나눈 부분 배열을 다시 분할한다.
function quickSort(arr, low = 0, high = arr.length - 1) {
if (low < high) {
const pivotIndex = partition(arr, low, high); // pivot 위치 찾기
quickSort(arr, low, pivotIndex - 1); // 왼쪽 부분 배열 정렬
quickSort(arr, pivotIndex + 1, high); // 오른쪽 부분 배열 정렬
}
return arr;
}
function partition(arr, low, high) {
const pivot = arr[low]; // 첫 번째 요소를 pivot으로 선택하는 경우
let left = low + 1;
let right = high;
while (left <= right) {
while (left <= high && arr[left] < pivot) left++; // pivot보다 큰 값 찾기
while (right > low && arr[right] >= pivot) right--; // pivot보다 작은 값 찾기
if (left < right) {
[arr[left], arr[right]] = [arr[right], arr[left]]; // Swap
}
}
[arr[low], arr[right]] = [arr[right], arr[low]]; // pivot과 right 위치 변경
return right; // pivot의 최종 위치 반환
}
console.log(quickSort([3, 6, 8, 10, 1, 2, 1]));pivot 선택에 따른 성능 차이
퀵 정렬의 성능은 pivot 선택 방법에 따라 크게 달라집니다.
최선의 경우 균형 잡힌 분할이 이루어지면 O(n log n)이지만, 최악의 경우 불균형한 분할이 이루어지면 O(n²)까지 성능이 떨어질 수 있습니다.
| pivot 선택 | 평균 시간 복잡도 | 최악의 경우 | 특징 |
|---|---|---|---|
| 마지막 요소 | O(n log n) | O(n²) | 정렬된 배열에서 최악의 성능 |
| 첫 번째 요소 | O(n log n) | O(n²) | 정렬된 배열에서 최악의 성능 |
| 랜덤 pivot | O(n log n) | O(n log n) | 항상 최적화된 성능 |
| 중간 요소 | O(n log n) | O(n log n) | 정렬된 배열에서도 좋은 성능 |
| Median of Three (중앙값 pivot) | O(n log n) | O(n log n) | 현실 코드에서 가장 안정적 |
이미 정렬된 배열에서, 첫 번째/마지막 요소를 pivot으로 선택하는 경우, 한쪽이 항상 pivot보다 크거나 작아서 한쪽만 계속 정렬되는 극심하게 불균형적인 분할이 일어납니다. 분할된 부분 배열은 0:n-1 혹은 n-1:0입니다. 이 때 재귀적으로 호출하는 트리 깊이가 n이 되므로 시간 복잡도는 O(n²)이 됩니다.
📌 점화식 Recurrence relation
pivot을 중심으로 항상 동일한 크기의 두 부분 배열로 분할되는 균등한 분할이 이루어질 경우, 점화식은 다음과 같습니다.
T(n) = T(n/2) 왼쪽 절반 + T(n/2) 오른쪽 절반 + Θ(n) 분할
T(n) = 2T(n/2) + Θ(n)- 크기가 절반으로 줄어든 두 개의 부분 배열에 대해 재귀 호출 = 각각 T(n/2)
- 현재 단계에서 분할(partitioning) 연산에 걸리는 시간 = Θ(n)
💡 점화식에서의 함수명
T(n)에서 T는 Time Complexity, n은 입력 크기를 뜻합니다.
점화식에서 사용하는 함수명은 시간(Time), 함수(Function), 개수(Count) 등 다양한 의미로 사용됩니다. 의미 있는 함수명으로 이해하기 쉽도록 만드는 것이 목적입니다.
- T는 시간 복잡도, T(n) = 2T(n/2) + O(n)
- F는 값을 반환하는 일반적인 함수, F(n) = F(n−1) + F(n−2)📌 마스터 정리 Master Theorem
마스터 정리는 분할 정복 divide-and-conquer 알고리즘의 점화식의 시간 복잡도를 계산하는 도구입니다.
마스터 정리의 기본적인 형태
T(n) = aT(n / b) + O(n^d)- 입력 크기 (n): 처리할 전체 입력 크기
- 부분 문제의 개수 (a): 해결해야 하는 부분 문제의 개수
- 각 부분 문제의 크기 (n/b): 나눠진 부분 문제들의 크기
- 재귀 외의 작업량 (O(n^d)): 재귀 호출 외에 해야 하는 작업의 복잡도
- ex) 문제를 나누거나 합치는 데 드는 시간
- log_b(a): 재귀 호출은 문제가 1이 될때까지(n/b이 1이 될 때까지) 반복됩니다. 이 과정이 반복되는 횏수가 log_b(a)입니다. b를 몇 번 곱하면 a가 되는지 구하는 연산입니다.
- ex) log_2(8) = 3
마스터 정리의 세 가지 케이스
| Case | 조건 | log_b(a) | 시간 복잡도 | 설명 |
|---|---|---|---|---|
| Case 1 | a > b^d | log_b(a) > d | O(n^log_b(a)) | 문제를 나누는 비용이 큼, 재귀 호출에서 발생하는 비용이 큽니다. |
| Case 2 | a = b^d | log_b(a) = d | O(n^d log n) | 문제 나누기 비용과 문제 해결 비용이 균형 |
| Case 3 | a < b^d | log_b(a) < d | O(n^d) | 문제 해결 비용이 더 큼, 재귀 호출에서 발생하는 비용보다 문제 해결 비용이 큽니다. |
마스터 정리 적용하기
T(n) = 2T(n/2) + Θ(n)퀵 정렬 점화식에서 a는 2, b는 2, d는 1입니다.
log_b(a)를 계산하면 log_2(2) = 1입니다. 이를 d와 비교했을 때, 동일하므로 Case 2에 해당하며, Case 2의 시간 복잡도는 O(n log n)입니다.
📌 합병 정렬 Merge Sort
- 주어진 배열을 동일한 크기의 두 부분배열로 분할
- 부분배열에 순환적으로 합병 정렬을 적용 (비순환적인 방식으로 진행할 수 있다.)
- 정렬된 배열을 합침
합병 과정
- 합병 과정의 시간 복잡도는 Θ(n)입니다.
function merge_sort(arr) {
let n = arr.length;
if (n <= 1) return arr;
// 분할
const mid = Math.floor(n / 2); // 중간 인덱스
const left = merge_sort(arr.slice(0, mid)); // 왼쪽 배열 정렬
const right = merge_sort(arr.slice(mid)); // 오른쪽 배열 정렬
// 병합
return merge(left, right, mid, n - mid, arr);
}
function merge(left, right, n, m, arr) {
let i = 0,
j = 0,
k = 0;
// left와 right를 비교하여 작은 값을 arr에 복사
while (i < n && j < m) {
if (left[i] < right[j]) {
arr[k++] = left[i++];
} else {
arr[k++] = right[j++];
}
}
// left 혹은 right에 남은 요소 복사
for (; i < n; i++) arr[k++] = left[i];
for (; j < m; j++) arr[k++] = right[j];
return arr;
}
console.log(merge_sort([3, 6, 8, 10, 1, 2]));특징
- 시간 복잡도는 O(n log n)입니다.
- T(n) = 2T(n/2) + O(n)
- T(n) = T(n/2) 왼쪽 절반 + T(n/2) 오른쪽 절반 + Θ(n) 합병
- 안정적인 정렬: 동일한 두 데이터에 대해서 항상 왼쪽 데이터를 먼저 선택한다.
- 제자리 정렬이 아님: 입력 크기 n 만큼의 공간이 필요
안녕하세요.