\(O(nlogn)\)정렬 알고리즘
⚠️ 원소들 사이의 비교를 지양하자는 아이디어로부터 등장한 알고리즘이다.
- 분할 정복 방식 (divide & conquer) 추구: 합병 정렬, 쾌속 정렬
- 트리 구조 이용: 힙 정렬
분할 정복 방식
➡️ 분할 정복의 3단계
1. 분할(Divide): 주어진 집합의 데이터를 적절한 크기의 부분 집합으로 나누고,
2. 정복(Conquer): 부분 집합에서 문제를 해결하여
3. 결합(Combine): 해결된 부분 해를 합쳐서 ⇒ 주어진 집합의 해를 구한다.
🚨 분할 정복 방식의 3가지 구성 요소
1. 같은 형식으로 문제를 해결할 것
2. 분할될 때마다 문제의 크기가 감소할 것
3. 예외적인 경우를 처리할 것
1. 합병 정렬(Merge Sort)
합병 정렬의 근거
💡
Q. 두 개의 정렬된 리스트를 하나의 정렬된 리스트로 합병하는 데 걸리는 시간은?
A. 두 리스트 각각의 가장 작은 수를 비교하여 더 작은 수를 정렬 리스트에 순서대로 저장한다. \(O(n)\)
간단한 예를 들면:
A = [1, 4, 7]
B = [2, 5, 6]
이미 정렬된 상태인 위의 두 리스트를 합쳐 정렬된 리스트 C를 만든다고 가정한다. 이 때 방법은:
[투 포인터 방식]
양쪽 리스트의 현재 인덱스를 가리키는 포인터를 사용하려 순차적으로 리스트를 병합한다.
1. A와 B의 첫 번째 원소(가장 작은 수)를 비교하여 더 작은 값을 C에 저장하고,
2. 그 값을 뺀 쪽의 인덱스를 한 칸 뒤로 이동한다.
3. 다시 두 리스트에서 현재 가리키고 있는 값을 비교하여 더 작은 값을 C에 넣는다.
4. 이 과정을 두 리스트 중 하나가 끝날 때까지 반복한 뒤에,
5. 남은 리스트의 요소들은 C에 그대롭 복사한다.
이 방법을 적용하면:
A포인터=0, B포인터=0
현재 비교 대상: A[0]=1, B[0]=2
더 작은 값인 A[0]=1을 C에 저장하고 A포인터는 한 칸 이동한다. (C = [1])
A포인터=1, B포인터=0
현재 비교 대상: A[1]=4, B[0]=2
더 작은 값인 B[0]=2을 C에 저장하고 B포인터는 한 칸 이동한다. (C = [1, 2])
A포인터=1, B포인터=1
현재 비교 대상: A[1]=4, B[1]=5
더 작은 값인 A[1]=4을 C에 저장하고 A포인터는 한 칸 이동한다. (C = [1, 2, 4])
A포인터=2, B포인터=1
현재 비교 대상: A[2]=7, B[1]=5
더 작은 값인 B[1]=5을 C에 저장하고 B포인터는 한 칸 이동한다. (C = [1, 2 , 4, 5])
A포인터=2, B포인터=2
현재 비교 대상: A[2]=7, B[2]=6
더 작은 값인 B[2]=6을 C에 저장하고 B포인터는 한 칸 이동한다. (C = [1, 2, 4, 5, 6])
B 리스트가 끝났으므로 A의 나머지 요소를 C에 저장한다. (C = [1, 2, 4, 5, 6, 7]) [완료]
이 방식이 가능한 이유는 두 리스트가 정렬되어 있기 때문임을 기억한다.
이 반복 과정에서 A와 B의 모든 원소를 정확히 한 번씩 확인하고 그 중 작은 값을 차례대로 C에 추가하는 구조가 된다.
🤔 시간 복잡도를 계산해보면
두 리스트가 있을 때, 두 리스트의 맨 앞 값을 비교해서 더 작은 수를 결과 리스트에 추가하는 과정을 반복한다. 한 쪽이 모두 소진되었을 때 남은 원소는 비교 없이 결과 리스트에 추가한다.
이 과정을 진행하는 동안 두 원소를 비교할 때마다 무조건 원소 1개가 결과 리스트에 추가된다. 각 리스트의 길이를 n1, n2라고 가정하면, 결국 결과 리스트에 총 n1 + n2 개의 원소가 저장되어야 하므로, 추가는 총 `n1 + n2` 번 일어난다.
비교의 경우 두 개의 리스트 중 하나가 먼저 소진되면 남은 리스트에 대해 더 이상 비교하지 않고 통째로 결과 리스트에 복사하여 저장하기 때문에 추가보다 적게 일어나게 된다. 그리고 끝까지 한 쪽이 소진되지 않고 비교되는 상황이 발생하더라도 한 쪽 리스트의 마지막 원소는 비교가 발생하지 않는다. 따라서 비교는 최대 `n1 + n2 - 1`번만 일어난다.
결과적으로 시간 복잡도는 \(O(n1+n2)\)로, 선형 시간이 된다.
합병 정렬의 원리
[5, 12, 4, 1, 2, 8, 2, 6, 10]
기존: 9개의 원소를 가진 정렬되지 않은 리스트 1개 → 9개의 원소를 비교 \(O(n^2)\) → 정렬
폰 노이만: 1개의 원소를 가진 정렬된 리스트 9개 → 정렬된 리스트를 합병 → 정렬
➡️ 분할 정복
1. 분할: n개의 원소를 가진 배열을 더 이상 분할할 수 없을 때까지 반복하여 2개로 분할한다.
→ n-1번 분할하게 되므로 \(O(n)\)
2. 정복: 더 이상 분할할 수 없는 배열은 정렬된 것으로 간주한다.
→ \(O(1)\)
3. 결합: n개의 원소를 가질 때까지 정렬된 배열을 합병하여 더 큰 정렬된 배열을 생성한다.
→ \(O(n)\)의 병합 연산을 \(logn\)번 수행하므로 \(O(nlogn)\)
합병 정렬 알고리즘 설계와 구현
🔑 핵심: 재귀 호출을 이용해 배열을 분할하고 병합한다.
- 정렬할 배열은 전역 변수로 선언하고, 함수에는 시작 인덱스(s)와 종료 인덱스(e)만 매개변수로 전달하여 구현의 효율성을 높인다.
- 더 이상 분할할 수 없는 기저 조건(`n == 1`)은 `s == e`로 판단할 수 있다.
→ 배열의 한 원소만 남았다는 뜻이므로 이때는 아무 작업도 하지 않고 그대로 반환한다.
int *arr; //정렬할 대상 배열 (전역 변수)
//병합 정렬 함수 - 매개변수: 정렬할 구간의 시작 인덱스(s)와 끝 인덱스(e)
void merge_sort(int s, int e) {
//[기저 조건] 구간에 원소가 1개뿐이면 정렬이 끝난 상태이므로 종료 (재귀 중지)
if(s == e) return;
//현재 구간을 절반으로 분할
int mid = (s + e) / 2;
merge_sort(s, mid); //왼쪽 절반 정렬 (재귀 호출)
merge_sort(mid+1, e); //오른쪽 절반 정렬 (재귀 호출)
//정렬된 두 부분 배열을 합병
merge(s, mid, mid+1, e);
}
//병합 함수: 정렬된 두 배열 [ls~le], [rs~re]를 하나로 합침
void merge(int ls, int le, int rs, int re) {
int lptr = ls; //왼쪽 배열 탐색 포인터
int rptr = rs; //오른쪽 배열 탐색 포인터
int bptr = 0; //임시 배열(brr) 인덱스 포인터
int size = re - ls + 1; //병합 후 총 원소 수
int *brr = (int*) calloc(size, sizeof(int)); //병합 결과를 담을 임시 배열 (0으로 초기화)
//양쪽 배열을 하나씩 비교하며 더 작은 값을 brr에 삽입
while (lptr <= le && rptr <= re) {
if (arr[lptr] < arr[rptr]) brr[bptr++] = arr[lptr++]; //왼쪽 값이 작으면 저장 후 왼쪽 포인터 이동
else brr[bptr++] = arr[rptr++]; //오른쪽 값이 작으면 저장 후 오른쪽 포인터 이동
}
//왼쪽 배열이 남았으면 전부 복사
while (lptr <= le) brr[bptr++] = arr[lptr++];
//오른쪽 배열이 남았으면 전부 복사
while (rptr <= re) brr[bptr++] = arr[rptr++];
//병합된 결과를 원래 배열(arr)에 덮어쓰기 (정렬된 상태로)
for (int i = 0; i < size; i++) {
arr[ls + i] = brr[i];
}
}
02. 쾌속 정렬(Quick Sort)
분할 정복 구조이지만 리스트를 적절하게 분할하여 합병 정렬과 달리 결합을 요구하지 않는다.
쾌속 정렬의 근거
💡 결합을 요구하지 않도록 리스트를 적절하게 분할하는 방법을 적용한다.
이 때 분할(Split)은:
- 기준이 되는 값(Pivot)을 중심으로
- Pivot 왼쪽에는 더 작은 값, 오른쪽에는 더 큰 값이 오도록 배치한다.
합병 정렬에서의 분할(Divide)은 기존 리스트를 단순히 2개의 리스트로 나누는 것이지만,
쾌속 정렬에서의 분할(Split)은 Pivot을 기준으로 왼쪽엔 작은 수, 오른쪽엔 큰 수만 배치하여 나눈다.
분할 알고리즘
🔑 핵심: left, right 두 포인터를 사용해 리스트를 스캔하면서 피벗보다 큰/작은 원소들을 교환한다.
- 피벗 기준으로 두 포인터를 양쪽에서 접근한다.
- 피벗보다 큰 값과 작은 값이 엇갈리면 서로 교환하고,
- 더 이상 교차하지 않으면 피벗과 오른쪽 포인터 값을 교환한다. ⇒ 피벗은 작은 값과 큰 값의 사이인 중심 지점으로 이동한다.
- 피벗이 이동한 인덱스를 기준으로 좌우 배열을 다시 재귀 정렬한다.
int split(int s, int e, int A[]) {
int pivot, left, right;
left = s+1; //피벗 다음 값부터 스캔 시작
right = e; //리스트 끝에서부터 역방향 스캔
pivot = A[s]; //기준이 되는 피벗 값: 리스트의 첫 번째 요소
while(left <= right) {
//피벗보다 작거나 같은 값을 만날 때까지 오른쪽 포인터를 왼쪽으로 이동
while((A[right] >= pivot) && (left <= right)) right--;
//피벗보다 크거나 같은 값을 만날 때까지 왼쪽 포인터를 오른쪽으로 이동
while((A[left] <= pivot) && (left <= right)) left++;
//두 포인터가 교차하지 않았으면 교환
if(left <= right) swap(A[left], A[right]);
}
swap(A[right], A[s]); //피벗을 가운데 위치로 이동
return right; //피벗이 위치한 인덱스 리턴 (피벗보다 작은 값의 끝 지점이 됨)
}예를 들어 적용하면:
A = [50, 10, 70, 30, 90]
pivot = 50
- 오른쪽 탐색
A[3] = 30 < 50 → 멈춤 → right = 3
- 왼쪽 탐색
A[2] = 70 > 50 → 멈춤 → left = 2
→ A[2]과 A[3]을 교환
→ A = [50, 10, 30, 70, 90]
그리고 while문 다시 반복
- 오른쪽 탐색
A[3] = 70 > 50
A[2] = 30 < 50 → 멈춤 → right = 2
- 왼쪽 탐색
A[2] = 30 < 50
A[3] = 70 > 50 → 멈춤 → left = 3
- left > right 이므로 반복 종료
→ swap(A[s], A[right]) //swap(A[0], A[2])
→ A = [30, 10, 50, 70, 90]
쾌속 정렬 알고리즘 구현
void quick_sort(int s, int e, int A[]) {
if(s >= e) return;
int m = split(s, e, A);
quick_sort(s, m-1, A);
quick_sort(m+1, e, A);
}
예를 들어 적용하면:
A = [3, 2, 1, 5, 8, 4, 3, 7]
//(a) return 2
quick_sort(0, 7, A); //pivot = A[0] = 3
right = 2 //A[2] = 1 < 3
left = 3 //A[3] = 5 > 3
//left > right이므로 두 원소 간 교환하지 않고 피벗 위치 교환만 수행하고 종료
[1, 2, 3, 5, 8, 4, 3, 7] //(a) split()의 결과
//(b) return 0 - 재귀 종료
quick_sort(0, 1, A); //pivot = A[0] = 1
right = 0 //끝까지 탐색 후 종료
left = 1 //A[1] = 2 > 1
//left > right이므로 두 원소 간 교환하지 않고 피벗 위치 교환만 수행하고 종료
[1, 2, 3, 5, 8, 4, 3, 7] //(b) split()의 결과
quick_sort(0, -1, A); //return
quick_sort(1, 1, A); //return
//(c) return 5
quick_sort(3, 7, A); //pivot = A[3] = 5
right = 6 //A[6] = 3 < 5
left = 4 //A[4] = 8 > 5
//left <= right이므로 스왑 후 또 반복
[1, 2, 3, 5, 3, 4, 8, 7]
right = 5 //A[5] = 4 < 5
left = 6 //A[6] = 8 > 5
//left > right이므로 두 원소 간 교환하지 않고 피벗 위치 교환만 수행하고 종료
[1, 2, 3, 4, 3, 5, 8, 7]
//(c) return 4
quick_sort(3, 4, A); //pivot = A[3] = 4
right = 4 //A[4] = 3 < 4
left = 5 //끝까지 탐색 후 종료 (left > right)
//left > right이므로 두 원소 간 교환하지 않고 피벗 위치 교환만 수행하고 종료
[1, 2, 3, 3, 4, 5, 8, 7]
//(d) return 7
quick_sort(6, 7, A); //pivot = A[6] = 8
right = 7 //A[7] = 7 < 8
left = 8 //끝까지 탐색 후 종료 (left > right)
//left > right이므로 두 원소 간 교환하지 않고 피벗 위치 교환만 수행하고 종료
[1, 2, 3, 3, 4, 5, 7, 8] //(e) 완료
🤔 시간 복잡도를 계산해보면
일단 퀵 정렬을 점근식으로 정의하면:
$$ T(n) = n -1+T(k-1)+T(n-k) $$
- n-1: pivot을 기준으로 n-1번 비교를 수행한다.
- T(k-1): pivot 기준 왼쪽 정렬
- T(n-k): pivot 기준 오른쪽 정렬
⇒ 배열을 분할하여 양쪽 부분을 재귀적으로 정렬한다.
그런데 퀵 정렬의 시간복잡도는 pivot을 어디서 선택하느냐에 따라 다르다.
최선 또는 평균적인 경우로 매번 pivot이 중간쯤(반)을 나누는 경우가 있다. 이 경우 한 번의 분할 단계에서 전체 n개 원소를 확인하며 pivot보다 작은 값과 큰 값을 나누는 과정이 필요하므로 한 단계의 연산량은 \(O(n)\)이다.
$$ T(n) = T(n/2)+T(n/2)+O(n)=2T(n/2)+O(n) $$
그리고 이렇게 반으로 나누는 작업이 재귀적으로 \(logn\)번 반복되므로 전체 시간 복잡도는:
$$ T(n) = O(nlogn) $$
그러나 최악의 경우 매번 pivot이 최솟값 또는 최댓값이 되는 상황이 발생할 수 있는데, 이 경우 분할된 배열 한쪽은 0개, 다른 쪽은 n-1개가 된다:
$$ T(n) = T(0)+T(n-1)+O(n)=T(n-1)+O(n) $$
그리고 이 식은 매번 pivot이 최솟값/최댓값이 되므로, 정렬해야 할 원소가 전혀 줄어들지 않고 항상 한쪽에만 n-1개의 원소가 남게 된다. 그래서 전체 배열이 한 칸씩만 줄어들면서 n, n-1, n-2, …, 1개의 원소에 대해 계속해서 한 방향으로만 재귀 호출되면서 정렬을 반복한다.
이처럼 한 번 정렬될 때마다 배열이 1칸씩만 줄어드는 구조는 n번 줄지어 일직선으로 재귀를 호출하는 것과 같으므로 이는 “선형적으로 재귀 호출되어” 결국 전체 시간 복잡도는:
$$ T(n)=O(n^2) $$
쾌속 정렬과 합병 정렬의 성능을 비교해보면
| 예 | 쾌속 정렬 | 합병 정렬 | |
| BEST | 5 1 6 3 4 8 7 2 | O(nlogn) | O(nlogn) |
| WORST | 1 2 3 4 5 6 7 8 8 7 6 5 4 3 2 1 |
O(n^2) | O(nlogn) |
| AVERAGE | 4 1 3 6 5 2 9 8 | O(nlogn) | O(nlogn) |
두 정렬 모두 평균적으로 \(O(nlogn)\)의 성능을 보여주지만, 많은 경우 쾌속 정렬이 합병 정렬보다 효율적이다.
기타 정렬
- 내부 정렬(Internal Sorting): 정렬할 자료를 메인 메모리에 올려서 정렬하는 방식
- 외부 정렬(External Sorting): 대용량의 보조 기억 장치를 이용해서 정렬하는 방식
쉘(Shell) 정렬
배열을 일정 간격(gap)으로 나누어 떨어진 원소끼리 삽입 정렬을 수행하는데, 간격을 점점 줄여가면서 마지막에는 `gap = 1`일 때 전체 삽입 정렬이 되도록 한다.
[2, 5, 3, 4, 3, 9, 3, 2, 5, 4, 1, 3]
//1. [gap = 6] 서로 6만큼 떨어진 항목끼리 삽입 정렬
a[0], a[6] → 2, 3 → 그대로
a[1], a[7] → 5, 2 → → 2, 5
a[2], a[8] → 3, 5 → 그대로
a[3], a[9] → 4, 4 → 그대로
a[4], a[10] → 3, 1 → → 1, 3
a[5], a[11] → 9, 3 → → 3, 9
//결과
[2, 2, 3, 4, 1, 3, 3, 5, 5, 4, 3, 9]
//2. [gap = 3] 서로 3만큼 떨어진 항목끼리 삽입 정렬
a[0], a[3], a[6], a[9] → 2, 4, 3, 4 → 2, 3, 4, 4
a[1], a[4], a[7], a[10] → 2, 1, 5, 3 → 1, 2, 3, 5
a[2], a[5], a[8], a[11] → 3, 3, 5, 9 → 그대로
//결과
[2, 1, 3, 3, 2, 3, 4, 3, 5, 4, 5, 9]
//3. [gap = 1] 삽입 정렬
[1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 9]
기수(Radix) 정렬
버킷(bucket)을 이용한 분배 방식 정렬로, 정렬할 원소를 버킷에 분배하는 과정을 반복한다.
[69, 10, 30, 2, 16, 8, 31, 22]
//10개의 버킷을 준비한다. (0 - 9)
//1. 1의 자리에 따라 버킷에 저장
[0] 10, 30
[1] 31
[2] 2, 22
[6] 16
[8] 8
[9] 69
//2. 각 버킷에 저장된 수를 정렬
[0] 10, 30
[1] 31
[2] 2, 22
[6] 16
[8] 8
[9] 69
//버킷에서 순서대로 꺼내 저장
[10, 30, 31, 2, 22, 16, 8, 69]
//3. 10의 자리에 따라 버킷에 저장
[0] 2, 8
[1] 10, 16
[2] 22
[3] 30, 31
[6] 69
//4. 각 버킷에 저장된 수를 정렬
//버킷에서 순서대로 꺼내 저장
[2, 8, 10, 16, 22, 30, 31, 69]
정렬의 성질
- Adaptive: 부분적으로 정렬된 데이터에 대해 더 좋은 성능을 보이는지
- Stable: 같은 값을 갖는 원소들이 자리를 바꾸는지
- In-place: 추가적으로 요구하는 메모리가 O(1)인지
- Online: 계속 증가하는 데이터에 대해 정렬이 가능한지
✅ 결론: 성능의 차이가 크므로 분할정복 정렬 알고리즘을 사용하자
'CS > 자료구조' 카테고리의 다른 글
| [k-mooc/자료구조] 01-07 복습 (4) | 2025.08.05 |
|---|---|
| [k-mooc/자료구조] 07. 트리(Tree) (3) | 2025.07.30 |
| [k-mooc/자료구조] 06-1. 정렬(Sorting) - O(N^2) 정렬 알고리즘 (2) | 2025.07.27 |
| [k-mooc/자료구조] 05. 스택/큐(Stack/Queue) (4) | 2025.07.26 |
| [k-mooc/자료구조] 04. 연결 리스트(Linked List) (2) | 2025.07.21 |