Divide and Conquer

• 입력을 나누어,
• 더 작은 문제를 풀고, (recursion)
• 작은 문제들의 답을 조합해
• 전체 문제의 답을 만드는 것

아주 작은 문제는 어쨌든 풀리기 때문이다.

그럼 어떻게 나눌까?

Recursive Merge Sort

Quick sort를 보기 전에 merge sort를 잠깐 보자. merge sort는 전형적인 D&C이고, NlogN 시간에 정렬할 수 있다.

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
}

Merge sort의 O()은 (NlogN)이다.
input data type에 관계없이 비교가 가능하다고 할 때, comparison model은 a1, a2, a3, … an이 있을 때, ai와 aj를 비교할 수 있다는 것을 의미한다. comparison model 안에서는 NlogN보다 빠른 시간에 sorting할 수 없다는 것은 증명되었다.

왜 그런지 간략히 설명하자면, N개의 데이터들로 받을 수 있는 입력의 수는 N!이다. sorting은 가능한 input 중에 어떤 것이 들어왔는지를 안다는 것을 의미하므로, ai < aj인지를 판별하는 질문에는 답이 Yes/No로 두 가지 밖에 없다.

최악의 경우에 가능한 입력들 중 절반을 버리므로 log(N!)번 질문을 버리게 된다. 이게 NlogN과 거의 비슷하므로 시간복잡도가 O(NlogN)인 것이다.

Quick sort

• Merge sort is good enough under O()
  • but allocating a new array is unavoidable and expensive
• Can we do O(NlogN) without allocating a new array?

// 완전한 코드는 아님!
int sort(int a[], int n) {
	// if n <= 5 do selection sort
	// else 
	int p = a[0]; // pivot: 기준. 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], a[j]); // pivot은 j번째 위치에 있게 됨
	sort(a, j); sort(a+j+1, n-j-i); // recursion
	return;
}

p는 pivot으로 기준점을 의미한다. input의 어떤 값으로 잡아도 되지만 일단 모르니까 가장 앞으로 잡아보자.

서커스의 결과로 원하는 결과는 pivot의 앞은 모두 pivot보다 작고, pivot의 뒤는 모두 pivot보다 크게 되는 것이다.

서커스가 끝나면 pivot은 더 이상 움직일 필요가 없다. 그리고 pivot 왼쪽의 값들이 pivot의 오른쪽으로 이동할 일도 없고, 반대도 마찬가지이다. 따라서 재귀 부분에서는 서커스 결과로 다시 배치된 pivot의 앞뒷부분을 각각 동일한 방법으로 sort하면 된다.

그럼 이제 서커스 부분을 보자.
pivot보다 작으면 pivot의 왼쪽에 있으면 된다. 그러니까 pivot보다 큰 값이 나올 때까지 계속 오른쪽으로 간다.

y: 최초로 만난 pivot보다 큰 값
x: 최초로 만난 pivot보다 작은 값

y와 x를 서로 바꿔준다. 이는 pivot보다 작은 값(x)은 pivot의 왼쪽으로, 큰 값(y)은 오른쪽으로 보내기 위함이다.

주의해야 할 점은 이 과정은 i < j일 때만 한다는 것이다. i와 j는 각각 pivot보다 크고 작은 값을 찾을 때까지 이동하기 때문에 i가 j보다 큰 상황이 발생할 수 있다. 이럴 때는 바꾸지 않아도 된다.

Merge sort와의 비교

merge sort에서는 무조건 절반씩 나누니까 logN을 보장할 수 있었는데 quick sort에서는 pivot을 무엇으로 잡냐에 따라 왼쪽/오른쪽이 크기가 달라지고 성능도 달라진다. O() 상으로도 다르다!

정리하면,

• Merge sort
  • 장점: O(NlogN)을 보장한다.
  • 단점: 배열을 추가적으로 할당해야 하기 때문에 시간이 오래 걸린다.
• Quick sort
  • 장점: 배열을 추가로 할당하지 않고 in-place에서 sort할 수 있다.
  • 단점: pivot을 무엇으로 잡느냐(또는 입력이 어떻게 주어지느냐)에 따라 성능이 많이 차이난다.

Performance

N개를 quick sort하는데 걸리는 시간을 Q(n)이라 하자.

• Worst case
  • pivot이 한 쪽 끝에 있는 경우
  • 나머지 N-1개를 sort해야 한다.
  • Q(N) = N + Q(N-1)이므로 Q(N) = O(N^2)이다.
• Best case
  • pivot이 배열을 반으로 나누는 경우
  • Q(N) = N + 2Q(N/2)으로 merge sort와 동일하게 Q(N) = O(NlogN)이다.
• Average case
  • 가장 간단한 정의는 모든 가능한 경우가 동일한 확률로 들어온다고 가정하는 경우
  • a[0]가 i등일 확률은 1/N이다.

  • 

  • 따라서 average case도 시간복잡도가 O(NlogN)이다.

Conclusion

• Quick sort almost always works in O(NlogN)
• worst case는 O(n^2)이지만 best case와 average case가 O(NlogN)으로 같다. 만약 worst case가 자주 발생했다면 average case가 best case에 가깝지 않았을 것이다.

Selection Problem

• In quick sort, can we find the best pivot?

• If we can do it in O(N), quick sort will run in worst case O(NlogN) time

• Selection problem: find the k-th smallest among a1, a2, …, aN
  • minimum, maximum, median, selection
• O(NlogN) is easy, just sort and look at the k-th
• but anything faster?

주어진 input에서 k번째로 가장 큰/작은 값을 구해보자. input을 sort해 앞에서부터 k번째 값을 찾으면 NlogN 시간에 완료할 수 있다. 하지만 값 하나를 찾기 위해 전체를 다 sort할 필요는 없다. k번째 수가 무엇인지 알기만 하면 되지 앞의 k-1개의 원소들과 뒤의 n-k개의 원소들 내에서의 대소관계에 대해서는 알 필요가 없기 때문이다. 실제로 selection problem을 사용하면 NlogN보다 빠른 시간에 문제를 풀 수 있다.

Approximate Median Problem

우리는 quick sort에서 pivot으로 중간값을 사용하는 것이 좋다는 것을 알았다. 그런데 selection에서도 중간값을 사용하는 것이 좋다!

정확한 중간값(median)을 찾는 것이 어려우므로 대략적인 중간값을 찾아보자.

• Find among a1, a2, …, a3, a member whose rank is between rn and (1-r)n
  • 0 < r < 1
  • let’s fix r at 0.3
• Quick sort works in O(NlogN) time with an approximate median as the pivot

approximate median과 selection을 각각 따로 O(NlogN)보다 빠르게 풀 수는 없다. 그러나 놀랍게도 동시에 풀면 O(NlogN)보다 빠르게 풀 수 있다!

Selection Strategy with Approximate Median

Quick sort style로 selection을 풀어보자.

• Find approximate median as P

• Divide array using P (as in quick sort)

• Recurse down with one of the the array
  • Quick sort recurses with both

Quick sort에서 pivot이 제 자리를 찾았을 때의 상황에서 시작하자.

우리는 현재 pivot이 몇 번째 위치에 있는지 알고 있다. 그렇기 때문에 만약 pivot의 위치가 k보다 작으면 pivot 앞쪽만 보면 되고, k보다 크면 pivot 뒤쪽만 보면 된다. 그래서 quick sort와 달리 한 쪽 배열만 보면 된다!

운이 좋게도 pivot이 k번째 위치에 있다면 더 이상 볼 필요가 없다. 이때 걸리는 시간은 S(N) = N + S(N/2) = N + N/2 + S(N/4) = … = O(N)

최악의 경우에는 S(N) = N + S(N-1) = N + (N-1) + S(N-2) = O(N^2).. merge sort보다도 나쁘지만 이런 경우는 거의 없다.

worst case를 피하려면 어떻게 할까? 여기서 approximate median이 등장한다.

approximate median을 찾았다고 가정하고, 찾는데 걸리는 시간을 A(N)이라 하면 S(N) = A(N) + N + S(0.7N)이다.

approximate median 중 최악의 경우는 가운데 40%의 맨 끝인 경우이다. 위에서 r=0.3으로 잡았으므로 배열의 앞 30%는 approximate median이 올 수 없다. 따라서 0.7N일 때 최악이다.

Approximate Median Strategy

• (Fixed r at 0.3)
  1. Divide into 5 members
  2. Sort each 5-member set
  3. Find real median X among the medians of 5 members
  4. X turns out to be an approximate median

먼저 입력을 5개씩 나누고 나눈 각 5원소 집합을 sort한다. 이 과정은 O(N) 시간에 할 수 있다.

그 다음, 각 집합에서의 중간값들을 모아 정렬하고, 정렬된 1/5N개의 값의 중간값을 구하고 이를 ★라 한다. (그림에서는 파란 동그라미)

그럼 ★가 답이다. 왜그럴까?

★의 왼쪽은 ★보다 작고, ★의 왼쪽은 ★보다 크다.

그럼 전체 입력중에서 ★보다 작은 원소는 몇 개 있는가?

절반 중 60%, 3/5이 ★보다 작고, 절반 중 60%, 3/5이 ★보다 크다. ★보다 작은 값이 최소 30% 있고, ★보다 큰 값이 최소 30% 있으므로 ★은 전체 입력 중 가운데 40%에 속하는 값이다.

Analysis of Selection with Approximate Median

N개의 데이터를 selection하는데 걸리는 시간 S(N)은 S(N) = A(N) + N + S(0.7N)이다. Approximate median을 구하는 시간 A(N)은 A(N) = N + S(0.2N)으로, A(N)과 S(N)은 동시에 풀린다.

A(N)을 대입해 S(N)을 다시 표현하면

S(N) = A(N) + N + S(0.7N) 
= N + S(0.2N) + S(0.7N)
= N + S(0.9N) = N + O(N)
(0.2N + 0.7N < 1N이므로 성립함)

S(N) = aN +b라 가정하면

O(N) = aN + b 
= N + (0.2aN + 0.2b) + (0.7aN + 0.7b)
= (1 + 0.9a)N + 0.9b

a=10, b=0, 즉 S(N)=10N이면 성립하므로 A(N)=3N이다.

따라서 S(N) = A(N) = O(N)이다.

The Whole Story and Conclusion

• Quick sort will run in worst case O(NlogN) time with O(N) approximate median algorithm
• But.. 실제로 approximate median으로 selection을 구현해보면 merge sort보다 느리다. 메모리를 할당때문에 복잡해지고 느려지고 O()에 상수도 붙고 그렇기 때문임.
• selection은 그래서 많은 경우에 그냥 sort해서 k번째를 찾는다.