분할통치법
(분할정복, divide-and-conquer)
세 단계를 통해 문제를 해결한다.
1. 분할 : 문제를 여러개로 분할 한다.
2. 재귀 : 분할된 개별 문제에 대해 재귀한다.
3. 통치 : 재귀로 해결된 개별 문제의 답을 합쳐 전체 문제의 답을 구한다.
합병정렬
분할통치 문제로 분석
통치 과정이 분할, 재귀 대비 복잡하다.
- 분할 : mergeSort 입력으로 들어온 무순리스트 L을 부리스트 L1, L2로 분할
- 재귀 : L1, L2에 대해 mergeSort 수행
- 통치 : 재귀를 거친 L1, L2를 merge하여 단일 유순리스트로 합병
성능
합병정렬의 동작을 이진트리로 도식화 할 수 있다. (합병정렬 트리)
실제로 트리를 만드는 것은 아니고 이해를 위해 사용하는 상상속의 트리이다.
합병정렬 트리의 유의미한 높이는 인데, 각 레벨마다 번 작업한다.
때문에 전체 트리의 작업시간은 이다.
n = 8, 높이
[높이] [소요시간]
5.8.6.1.3.2.7.4 4 ↑ O(n)
/ \ |
5.8.6.1 3.2.7.4 3 logn O(n)
/ \ / \ |
5.8 6.1 3.2 7.4 2 ↓ O(n)
/ \ / \ / \ / \
5 8 6 1 3 2 7 4 1 일반 리스트에 대한 알고리즘
Alg mergeSort(L)
input list L with n elements
output sorted list L
1. if(L.size() > 1)
L1, L2 ← partition(L, n/2)
mergeSort(L1)
mergeSort(L2)
L ← merge(L1, L2)
2. return
----------------------------
Alg merge(L1, L2)
input 정렬된 리스트 L1, L2
output L1, L2가 합쳐진 하나의 정렬된 리스트
1. L ← 빈 리스트
2. while(!L1.isEmpty() & !l2.isEmpty())
if(L1.get(1) <= L2.get(1))
L.addLast(L1.removeFirst())
else
L.addLast(L2.removeFirst())
3. while(!L1.isEmpty())
L.addLast(L1.removeFirst())
4. while(!L2.isEmpty())
L.addLast(L2.removeFirst())
5. return배열에 대한 알고리즘
Alg mergeSort(A)
input n개 키의 배열 A
output 정렬된 배열 A
1. rMergeSort(A, 0, n-1)
2. return
-----------------------
Alg rMergeSort(A, l, r)
input 배열 A[l..r]
output 정렬된 배열 A[l..r]
1. if(l<r)
m ← ⌊ (l+r)/2 ⌋
rMergeSort(A, l, m)
rMergeSort(A, m+1, r)
merge(A, l, m, r)
2. return
-----------------------
Alg merge(A, l, m, r)
input 정렬된 배열 A[l..m], A[m+1..r]
output 정렬된 하나의 배열 A[l..r]
1. B ← r-l+1 크기의 빈 배열 # 병합할 임시 배열
i, k ← l # i는 L1에 대한 인덱스, k는 L2에 대한 인덱스
j ← m+1 # j는 B에 대한 인덱스
2. while(i<=m & j<=r)
if(A[i] <= A[j])
B[k++] ← A[i++]
else
B[k++] ← A[j++]
3. while(i<=m)
B[k++] ← A[i++]
4. while(j<=r)
B[k++] ← A[j++]
5. for k ← l to r
A[k] ← B[k]
6. return퀵소트
분할통치 문제로 분석
피봇을 결정하고 분할하는 과정이 재귀,통치 대비 복잡
- 분할 : 피봇p를 정하고, quickSort 입력으로 들어온 리스트 L을 p를 기준으로 3개의 부리스트로 분할
1-1. LT : p보다 작은 원소들
1-2. EQ : p와 같은 원소들
1-3. GT : p보다 큰 원소들 - 재귀 : 분할된 세 조각에 대해 quickSort수행
- 통치 : LT, EQ, GT 결합 (각각은 모두 정렬되어있으므로 LT-EG-GT순으로 결합하면 전체적으로도 정렬된 상태의 리스트가 됨)
피봇 결정
퀵소트 재귀 과정에서 리스트를 분할할 때 가능하면 균등한 크기로 나누는 것이 성능상 좋다.
만약 피봇을 잘못 고르면 LT, GT중 하나가 너무 길어져서 성능이 낮아진다.
- 결정적(Deterministic)인 방법 (Critical 아님)
- 맨 앞 또는 맨 뒤 또는 중간 원소 선택
- 균등하게 구간을 나눠 선택한 원소들의 중앙값(median) 원소 선택
→ (예시) 0*(0/2)번째, 1*(1/2)번째, 2*(2/2)번째 원소의 중앙값
- 무작위한 방법
성능 분석
병합 정렬-성능과 마찬가지로 '퀵 정렬 트리'로 도식화할 수 있다.
성능이 최악일 경우는 n개 원소를 분할했을 때 LT, GT 한 쪽에 n개가 모두 몰렸을 때 이다. (분할해서 해결하는 의미 자체를 잃어버린다.)
--> 이 경우 n번의 분할이 일어나고, 퀵정렬 트리의 각 레벨마다 n번 작업한다.
-->
이보다는 실제로 동작하는 '기대 실행 시간'으로 퀵소트를 평가하는 것이 적절하다.
LT, GT의 크기가 '일정 크기'보다 작으면 좋은호출, 그렇지 않으면 나쁜호출로 분류할 수 있다. 호출이 좋을 확률은 1/2이다. (어차피 결과적으로는 좋거나, 나쁘거나 둘 중 하나이므로)
--> 이 경우 logn번의 분할이 일어나고, 퀵정렬 트리의 각 레벨마다 n번 작업한다.
-->
따라서 아래와 같이 정리할 수 있다.
- 최악 실행 시간 :
- 기대 실행 시간 :
제2의 공간을 사용하는 알고리즘
Alg quickSort(L)
input n개 원소를 가진 리스트 L
output 정렬된 리스트 L
1. if(L.size()>1)
k ← L 범위 내의 1개 위치 (L에서 고를 pivot의 위치)
LT, EQ, GT ← partition(L, k)
quickSort(LT)
quickSort(GT)
L ← merge(LT, EQ, GT)
2. return
------------------------------
Alg partition(L, k)
input n개 원소를 가진 리스트L, 피봇 위치 k
output 분할된 부리스트 LT, EQ, GT
1. p ← L.get(k)
LT, EQ, GT ← 빈 리스트
2. while(!L.isEmpty())
e ← L.removeFirst()
if(e<p)
LT.addLast(e)
else if(e=p)
EQ.addLast(e)
else
GT.addLast(e)
3. return LT, EQ, GT제자리 정렬 알고리즘
Alg inPlaceQuickSort(L, l, r)
input 리스트 L, 위치 l r
ouput 정렬된 리스트 L
1. if(l>r)
return
2. k ← l~r 범위 내의 한 위치
3. a, b ← inPlacePartition(L, l, r, k)
4. inPlaceQuickSort(L, l, a-1) # a는 EQ의 시작 지점
inPlaceQuickSort(L, b+1, r) # b는 EQ의 끝 지점
-------------------------
** 입력리스트L이 유일한원소로 구성된 배열A라고 가정한 partition함수
Alg inPlacePartition(L, l, r, k)
input 배열 A[l..r], 인덱스 l r k
output 피봇위치 i
1. p ← A[k]
2. A[k] ←→ A[r] # 피봇 원소 맨 뒤로 치워놓기
3. i ← l
j ← r-1
4. while(i<=j)
while(i<=j & A[i]<=p) # A[i]가 피봇보다 커지면 탈출
i ← i+1
while(i<=j & A[i]>=p) # A[j]가 피봇보다 작아지면 탈출
j ← j+1
if(i<j) # i가 j보다 왼쪽이면 스왑, 아니면 끝
A[i] ←→ A[j]
5. A[i] ←→ A[r] # 치워놓았던 피봇 제자리로
6. return i위 알고리즘의 inPlacePartition(A, l, r, k)는 배열A가 유일한 원소로 이루어졌다고 가정한다. 즉, LT, GT, 하나의 pivot으로 분할할 수 있다. 리턴값이 i하나인데, pivot의 위치이다.
만약 배열A(리스트 L)이 중복된 원소가 있다면 효율적인 해결을 위해 3-way partitioning 을 사용해야 한다. 그러면 LT, GT, EQ 세 부리스트로 빠르게 분할할 수 있다. (만약 위의 알고리즘을 그대로 적용하면 비효율적으로 수행한다.)
3-way partitioning의 C언어구현은 아래와 같다.
- 참고자료 퀵 정렬
void QuickSort(int* A, int l, int r) {
if(l>r) return;
int k = findPivot();
int a=0, b=0;
inPlacePartition(A, l, r, k, &a, &b);
rQuickSort(A, l, a - 1);
rQuickSort(A, b + 1, r);
}
void inPlacePartition(int* A, int l, int r, int k, int* a, int* b) {
// A:정렬대상 배열 , l:left, r:right, k:pivot, a b:분할 결과
int pivot = A[k];
int i = l; // 오른쪽으로 이동하는 커서
int lt = l; // 오른쪽으로 이동하는 커서. i보다 왼쪽.
int gt = r; // 왼쪽으로 이동하는 커서. i보다 오른쪽.
while (i <= gt) { // i > gt이면 반복문 끝
if (pivot == A[i]) {
i++;
}
else if (A[i] < pivot) {
swap(&A[lt], &A[i]);
lt++;
i++;
}
else if (A[i] > pivot) {
swap(&A[gt], &A[i]);
gt--;
}
}
// 이 라인을 읽는 시점에 lt부터 gt까지 정렬 완료.
// --- 이제 0 ~ a-1구간, b+1 ~ n-1구간에 대해 정렬을 이어가면 됨.
*a = lt;
*b = gt;
}정렬 일반
5가지 정렬 요약비교
- 시간 복잡도
- 선택정렬 :
- 삽입정렬 :
- 힙 정렬 :
- 합병정렬 : (성능을 유지하면서 제자리 정렬 불가)
- 퀵 정렬 : (기대실행시간)
정렬의 안정성
정렬하려는 리스트속에 중복된 원소가 있을 수 있다.
1 2 3 2 4
여기서 첫 번째 2를 a, 두 번째 2를 b라고 하자
1 a 3 b 4
위 리스트에 정렬을 수행했을 때 두 가지 경우가 나올 수 있다.
- a, b 순서가 유지된 경우 : 1 a b 3 4
- a, b 순서가 파괴된 경우 : 1 b a 3 4
순서가 유지되도록 수행하는 정렬 알고리즘을 '안정적이다'라고 표현한다.
반대로 유지가 되지 않는 알고리즘을 '불안정하다'라고 표현한다.
- 안정 정렬의 예 : 삽입정렬 합병정렬
- 불안정 정렬의 예 : 선택정렬 퀵정렬 힙정렬
