[알고리즘] Binary Search, Mergesort(DIvide and Conquer)

DIvide and Conquer Approach

- Divide : 인스턴스가 너무 커서 계산이 힘들다면 작게 쪼개서 계산한다.

- Conquer : 작아진 인스턴스를 해결한다.

- Combine : 해결한 인스턴스를 재조립한다.

-> Top-down approach(하향식 접근법)

Binary Search Algorithm Design

- 검색 범위를 줄여가며 탐색

- Problem : 크기가 n인 sorted array S에서 key x는 어디에 있는가?

- Input(parameter) : 양수 n, 1부터 n까지의 값을 갖고 있는 정렬된 내림차순이 아닌 배열 S(sorted array)

      + non-decreasing order(비내림차순) : 내림차순이 아니다 != 오름차순

      ex. 1, 5, 6, 5, 10을 정렬하면 5가 있기 때문에 내림차순이 아님

- Output : S에서의 x의 위치(x값이 없으면 0)

- Design Strategy

   -> Divide : 배열을 반으로 나눠서 x가 가운데 항목보다 작으면 왼쪽 부분 배열을, x가 크면 오른쪽 부분 배열을 선택

   -> Conquer : 선택한 array에 x가 있는지 판단하여 정복? | 배열이 충분히 작지 않다면 재귀를 사용하여 진행

   ->  Combine : 아무튼 잘 합쳐줍니다?

//Binary Search (Recursive algorithm)

index location (index low, index high) {
	index mid;
    
    if(low > high)
    	return 0; 			//not found
    else {
    	mid = (low + high) / 2		//중간 값 찾기
        if( x == S[mid])
        	return mid; 		//found
        else if(x < S[mid])
        	return location(low, mid - 1) //왼쪽 array 선택
        else
        	return location(mid + 1, high) //오른쪽 array 선택
        }
    }
    
    ...
    locationout = location(1, n);
    ...

Worst Case Time Complexity

case1. 짝수인 경우

반으로 나눠서 순차적인 계산 W(n/2)와 반으로 쪼개는 과정 + 1

 

 

 

 

 

 

WCTC : Proof for case1.

n = 1 인 경우 w(1) = 1 = lg 1 + 1

 

음 그렇군.

 

 

 

Case 2. 홀수인 경우 

n이 홀수라면 floor function(바닥함수)로 n을 지정해줌

 

divide할 경우 짝수는 반으로 나누면 나눠진 배열이 한 쪽은 홀수가 되기 때문에 고려해서 계산해줌.

floor function으로 계산하기 때문에 결과에 그렇게 큰 차이는 없는 것 같군요

WCTC : Proof for case 2.

짝수 홀수

Mergesort

- 잘게 쪼개서 합치면서 비교하며 정렬

- Problem : n개의 key를 감소하지 않게(nondecreasing) 정렬하기

- Input(parameter) : 1부터 n까지의 값이 들어있는 배열 S, 양의 정수 n

- Output : 감소하지 않게 정렬된 배열 S

- Design Strategy

  -> Divide : 배열을 n/2의 item을 갖고 있는 subarray로 쪼개주기

  -> Conquer : 정렬하여 합치기 | 배열이 충분히 작지 않다면 재귀로 더 잘게 쪼개주기

  -> combine : 정렬된 배열로 정리하기

void mergeSort(int n, keytype S[])
{
	int h, m;
    keytype U[], V[];
    if(n > 1) {
    	h = n / 2; //floor function 아무튼 중간 값으로 쪼개기
        m = n - h //쪼개진 뒷 부분 배열의 시작
        
        copy S[1] thru S[h] to U[1] thru U[h]; //S[1]에서 S[h]까지 값을 U[]에 넣어줌 < 중간 기준 앞 배열
        copy S[h+1] thru S[n] to V[1] to V[m]; //S[h+1]에서 S[n]까지 값을 V[]에 넣어줌 < 중간 기준 뒷 배열
        
        //왕창 쪼갬
        mergesort(h, U);
        mergesort(m, V);
        //합침
        merge(h, m, U, V, S);
        }
}

void merge(int h, int m, const keytype U[], const keytype V[], const keytype S[]) {
	index i = 1, j = 1, k = 1;
    while(i <= h && j <= m) {
    	if(U[i] < V[j]){ S[k] = U[i]; i++ }
        else { S[k] = V[j]; j++ }
        k++; 
        //더 큰 값 넣어주기
    }
    if(i > h)
    	copy V[j] through V[m] to S[k] through S[h+m];
    else
    	copu U[i] through U[h] to S[k] through S[h+m];
    //다 쓴 배열 있으면 나머지 배열 넣어주기?

Example

arrays U와 arrays V를 array[S]에 merging하는 경우

 

 

 

 

Worst Case Time Complexity : Merge

- Basic operation : U[i]와 V[j]의 비교

- Input으로 h랑 m을 넣은 2개의 arrays

worst case는 i = h, j = m - 1 에서 w(h, m) = h + m - 1

뭔소린지 모르겠음.

 

Worst Case Time Complexity : Mergesort

- Analysis

 W(h, m) = W(h) + W(m) + h + m - 1 //왼쪽 배열 + 오른쪽 배열 + merge h & m

 

 

 

Space Complexity Analysis

In-place sort

: extra space를 사용하지 않는 정렬

Mergedort() -> 반으로 나누고 나누고 나누면서 계속 배열을 생성함

∴S(n) = 2n ∈ Θ (n)

 

 

Space를 줄이기 위한 방법 (2n -> n)

Mergesort2

//mergesort2

void mergesort2(index low, index high) {
	index mid;
    if(low < high) {
    mid = (low + high) / 2; //중간값 설정
    mergesort2(low, mid); //왼쪽 배열 정렬
    mergesort2(mid + 1, high); //오른쪽 배열 정렬
    merge2(low, mid, high); //merge함?
    }
}

Merge2

//Merge2

void merge2(index low, index mid, index high) {
	index i = low, j = mid + 1, k = low; //i는 가장 작은 값, j는 다음 배열 값, k는 작은 값
	keytype U[low..high];
	while(i <= mid && j <= high) { //둘 다 전부 확인한 상태가 아니라면
    	if(S[i] < S[j]) { U[k] = S[i]; i++} //더 작은 값을 U[]에 넣기
        else {U[k] = S[j]; j++}
        k++;
    } //전부 다 끝난 후
    if(i > mid) //i에 남아있는 값이 있다면
    	copy S[j] through S[high] to U[k] through U[high]; //U[]에 남은거 넣기
    else
    	copy S[i] through S[mid] to U[k] through U[high];
    copy U[low] through U[high] to S[low] through S[high]; //새로 정렬한 값을 기존 배열에 넣어주기
}