Divide and Conquer - Merge Sort / Quick Sort

Merge Sort

int sort(int a[], int n)
{
	int h;
	int b[n];
	h = n/2;
	// copy a[] to b[]
	sort(b, h);
	sort(b+h, n-h);
	// Merge two halves in b to a
	return;
}

::시간 복잡도::
재귀 n번 * 이진 분할
=> O(nlogn)

::정렬에는 최소 O(nlogn) 시간이 걸리는 이유::
n 개를 비교 정렬하는 결정 트리가 있다고 하자.
nPn = n! 의 가능한 결과가 결정 트리의 잎으로 존재하게 된다.
이때 결정 트리는 이진 트리이기 때문에 최소 높이가 log(n!) 이 된다.
즉 최소한 log(n!)는 내려가야 결과를 얻을 수 있다는 의미이다. n! 는 근사시 n^n 이므로,
따라서 정렬에는 최소한 O(nlogn)의 시간이 걸린다.

Algorithm] 비교 정렬의 하한

배열 Allocating으로 인한 시간 소요 발생!
Allocating을 하지 않는다면 시간을 더 줄일 수 있지 않을까?
⇒ Quick Sort

 

 

2751번: 수 정렬하기 2

---

Quick Sort

int sort(int a[], int n){
    // if n <= 5 do selection sort
    // else
    int p = a[0];
    int i = 1; int j = n-1;
    while(i < j){
        while(a[i] < p) i++;
        while(a[j] > p) j--;
        if(i < j) swap a[i], a[j];
    }
    swap a[0] and a[j];
    sort(a, j); sort(a+j+1, n-j-1);
    return;
}

• Quick Sort 진행 방식
  • a[0]를 pivot으로
  • pivot 보다 작은 애들은 다 왼쪽으로, 큰 애들은 다 오른쪽으로
  • i >= j 가 되어 서로 교차되면 가운데(pivot 보다 작다) 랑 pivot 이랑 swap
  • 왼쪽 부분 재귀, 오른쪽 부분 재귀

::시간 복잡도::
최악의 경우 :
pivot 이 가장 왼쪽, 오른쪽 끝에 들어가면 정렬되는 것이 별로 없다.
O(n²)

최고의 경우 :
pivot이 거의 중간쯤에 잡힐 때 ⇒ Merge sort 랑 비슷할 때
O(nlogn)
(Allocating을 하지 않으므로 이 경우 Merge sort보다 빠르다.)

평균 :
모든 가능한 입력에 대한 기댓값 (likely equally)
n! 에 대한 가능한 입력이므로 ⇒ 1/n! 의 확률
O(nlogn)

어쨌든 평균 O(nlogn) 이 걸린다!

 

---

Selection Problem

• Quick sort의 pivot이 가운데에서 잡힐수록 Best. O(nlogn)
• 가운데에서 잡히는 pivot을 찾는 방법.
• 정렬 O(nlogn) 없이 O(n) 안에 k 등을 찾을 수 있다.

1 등 찾기 : n번 훑기 ⇒ O(n)
2 등 찾기 : 2개씩 묶어서 토너먼트 ⇒ 2등은 1등에게 진 logn 중에 존재. ⇒ O(n + logn)
3 등 찾기 : 토너먼트에서 2등에게 진 녀석.

 

---

The Approximate Median Problem

• 정확한 pivot의 위치를 구하지 말고 범위를 구하자.
• 그 범위 안에서도 Quick sort는 여전히 O(nlogn) 일 것이다.

a1, a2, ..., an의 원소에서 pivot의 범위는
rn ~ (1-r)n 사이에 존재.

이때 0 < r < 1이며 여기서는 r = 0.3으로 고정.

따라서 pivot 은 0.3n ~ 0.7n 사이에 존재하고
이는 가운데 40% (0.4n)를 차지하는 비율이다.

 

---

Selection Strategy with Approximate Median

1. pivot에 대한 Approximate Median을 찾는다.
2. 위의 pivot을 사용해서 Quick sort에서 했던 것처럼 배열을 나눈다.
3. selcetion 하고자 하는 k 등 수가 pivot 등 수 보다 크면 오른쪽 배열만 재귀한다.
   pivot 등 수보다 작으면 왼쪽 배열만 재귀한다.

평균 :
n을 중간에서 반으로 갈라서 한쪽만 재귀하므로

n + n/2 + n/4 + … = {1/(1-1/2)}n = 2n
⇒ O(n)

최악의 경우 :
Approximate를 안 했을 땐
⇒ O(n²)

그러나 Approximate에 의해 적절한 중간 범위에서 n이 반으로 갈라지므로
n + 0.7n + (0.7)^2n + … = {1/(1-0.7)}n = (10/3) n
⇒ O(n)

따라서 최악의 경우에도 O(n) 이 나온다!

 

---

Approximate Median Strategy

• pivot에 대한 Approximate Median 찾기.

1. r = 0.3으로 고정한다.

2. 배열을 5개 씩의 묶음으로 나누기 ⇒ O(n)
(5라는 수는 r과 관련이 있다.)

3. 각각의 5개 묶음 안에서 정렬 ⇒ O(n)

4. 정렬된 묶음 내부에서 Median을 뽑기
총 n/5개 존재.

5. 뽑은 Median 들 중 에서의 Median X를 고르기
(Selection(n/5)을 사용하여 Median X를 찾는다.)

6. 정렬된 묶음들을 세로로 나열한다. (작은 게 밑으로 가도록)
세로로 나열된 묶음들을 봤을 때 묶음 간의 대소관계는 불확실하지만,
X의 왼쪽 묶음들 중 X보다 아래쪽은 전부 X보다 작다.
X의 오른쪽 묶음들 중 X보다 위쪽은 전부 X보다 크다.

8. 따라서 이러한 작고 큰 것들이 전체에서 양옆으로 30% 나타나기 때문에
⇒ 찾은 X는 0.3n ~ 0.7n의 범위 내에서만 존재한다.

즉, Approximate Median을 만족한다.

 

---

Analysis of Selection with A-M

flowchart TD q1("S(n)") q2("A(n)") q3(n) q4("S(0.7n)") q5(n) q6("S(n/5=0.2n)") q1-->q2 q1-->q3 q1-->q4 q2-->q5 q2-->q6

 

S(n) = S(0.2n) + S(0.7n) + n

이때 S(n) = an +b라고 가정하면 an + b = 0.2an + b + 0.7an + b + n an + b = 10n (a = 10, b = 0)
따라서 S(n) = O(n)

이후 Quick Sort에 적용하면 최악의 경우에도 O(nlogn) 이 나온다!!

근데 평균이 MergeSort 보다 느려져서 이 알고리즘은 잘 안 쓴다. 헉!