11. divide and conquer, quick sort [5 1주차]

11. Divide and Conquer, Quick Sort [5-1주차]

2024년 1월 13일 토요일

오후 6:42

<Divide and Conquer>

1.     입력을 나누어

2.     더 작은 문제를 풀고

3.     작은 문제들의 답을 조합하여

4.     전체 문제의 답을 만든다

 

아주 작은 문제는 어쨌든 풀린다.

어떻게 나눌 것인가?

 

 

<Recursive 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이 된다.

 

이처럼 특수한 경우에는 nlogn보다 빠른 정렬이 존재한다. 일반적인 경우에도 nlogn보다 빠른 정렬이 존재할까?

 

 

<O(nlogn) 보다 빠른 정렬이 있는가?>

최악의 경우 nlogn보다 빠른 모든 상황에서 쓸 수 있는 정렬은 없다.

모든 상황에서 쓸 수 있는 정렬 -> 내부 내용은 볼 수 없고 비교만 가능하다고 가정

 

배열의 내용은 1부터 n까지를 섞은 것으로 가정한다. n! 가지의 서로 다른 입력이 가능하다. 이 n!중 어떤 입력이 들어왔는지를 밝혀내면 정렬을 할 수 있다. 비교를 한번 할 때마다, n! 가지의 경우 중 절반씩 버릴 수 있다. 따라서 하나를 남기려면 log(n!) ~= nlogn번의 비교가 필요.

 

 

<Quick sort가 빠른 이유>

최악의 경우에는 merge sort가 quick sort보다 점근적으로 더 빠르다. 그러나 merge sort에서는 배열을 적어도 하나 더 만들어야 한다. 정렬해야 할 원소의 개수가 많을수록, 새 배열을 할당하는 데 훨씬 많은 시간이 걸릴 수 있다. 새 배열을 할당하지 않고 nlogn 정렬을 하기 위해 quick sort가 개발되었다.

 

 

<알고리즘 시간복잡도에서 최악의 경우를 많이 쓰는 이유>

1.     분석하기 그나마 편함

2.     대부분의 데이터에 최악의 경우가 많음

 

그러나 quick sort에서는 최악의 경우로 계산하는 것이 실제와 많이 다르다.

 

 

<quick sort>

int sort(int a[], int n) {

if(n <= 5)

selection sort;

return;

 

int p = a[0];  // 인덱스 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의 성능>

Worst Case : O(n²) 끝에서 나눠지는 경우

Best Case : O(nlogn) 절반식 나눠지는 경우

Average Case : 모든 입력에 대한 실행 시간의 기댓값. 모든 입력의 확률이 각각 같다고 가정.

 

 

<Average Case Quick Sort>

n!의 모든 경우를 생각할 필요 없이, 피벗이 1등인 경우, 2등인 경우, … , n등인 경우로만 나누어 생각할 수 있다.

E(n) : n개를 정렬하는 데 걸리는 시간의 기댓값

 

E(n) = 1/n { (E(0) + E(n-1)) + (E(1) + E(n-2)) + … + (E(n-1) + E(0)) } + n

      = 2/n ( E(1) + … + E(n-1) ) + n

nE(n) = 2( E(1) + … + E(n-1) ) + n²

(n-1)E(n-1) = 2( E(1) + … + E(n-2) ) + (n-1)²

nE(n) - (n-1)E(n-1) = 2E(n-1) + n² - (n-1)²

nE(n) = (n+1)E(n-1) + 2n - 1

E(n)/(n+1) = E(n-1)/n + (2n-1)/n(n+1) = E(n-1)/n - 1/n + 3/(n+1)

E(n)/(n+1) = - ∑[1~n] 1/k + ∑[1~n] 3/(k+1) = O(logn)

 

대부분의 경우 O(nlogn)