분할 검색 - 개념과 병합 정렬

• 분할 정복
• 병합 정렬

분할 정복

분할 정복 기법

유래

• 1805년 12월 2일 아우스터리츠 전투에서 나폴레옹이 사용한 전략
• 전력이 우세한 연합군을 공격하기 위해 나폴레옹은 연합군의 중앙부로 쳐들어가 연합군을 둘로 나눔
• 둘로 나뉜 연합군을 한 부분씩 격파함

설계 전략

• 분할 (Divide) : 해결할 문제를 여러 개의 작은 부분으로 나눈다
• 정복 (Conquer) : 나눈 작은 문제를 각각 해결한다
• 통합 (Combine) : (필요하다면) 해결된 해답을 모은다

Top-down approach

반복 (Iterative) 알고리즘 O(n)

Interative_Power(x, n)
    result = 1

    FOR i in 1 -> n
    result = result * x

    RETURN result

분할 정복 기반의 알고리즘 O(logn)

C^n을 구하기 위해서는?

Recursive_Power(x, n)
	IF n == 1 : RETURN x;
	IF n is even
		y = Recursive_Power(x, n/2)
		RETURN y*y
	ELSE
		y = Recursive_Power(X, (n-1)/2)
		RETURN y * y * x

병합 정렬

• 여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방식
• 분할 정복 알고리즘 활용
  • 자료를 최소 단위의 문제까지 나눈 후에 차례대로 정렬하여 최종 결과를 얻어냄
  • top-down 방식
  • 안정 정렬
• 시간 복잡도: O(nlogn)

병합 정렬 과정

• {69, 10, 30, 2, 16, 8, 31, 22} 를 병합 정렬하는 과정
• 분할 단계: 전체 자료 집합에 대하여, 최소 크기의 부분집합이 될 때까지 분할 작업을 계속한다

• 병합 단계: 2개의 부분 집합을 정렬하면서 하나의 집합으로 병합
• 8개의 부분집합이 1개로 병합될 때까지 반복함

알고리즘: 분할 과정

mergeSort(arr[], left, right) {
    IF left < right:
        mid = (left+right) / 2
        mergeSort(arr, left, mid)
        mergeSort(arr, mid+1, right)
        merge(arr, left, mid, right)

알고리즘: 병합 과정

merge(arr[], left, mid, right) {
    L = left
    R = mid+1
    idx = left
    while L <= mid && R <= right {
        if arr[L] <= arr[R]
            sortedArr[idx++] = arr[L++]
        else
            sortedArr[idx++] = arr[R++]
    }
    if L <= mid {
        for i in L to mid
            sortedArr[idx++] = arr[i]
    } else {
        for j in R to right
            sortedArr[idx++] = arr[j]
    }
    for i in left to right
        arr[i] = sortedArr[i]