분할 정복

2.1 Binary search

이분 검색

• 분할 정복(Divide-and-Conquer)
• 으로 원소를 찾아보자😎
• [Divide] 정가운데 원소를 기준으로 S를 두 개의 리스트로 분할
• [Conquer] x가 정가운데 원소보다 크면 오른쪽, 작으면 왼쪽을 재귀 호출
• [Obtain] 선택한 리스트에서 얻은 답을 리턴

Binary search

def location (S, low, high):

    if (low > high):
        return 0

    else:

        mid = (low + high) // 2
        if (x == S[mid]):
            return mid
        elif (x < S[mid]):
            return location(S, low, mid - 1)
        else:
            return location(S, mid + 1, high)

2.2 Merge sort

merge sort도 Divide and Conquer로 풀어보쟈 😎

• [Divide] 원소가 n개인 S를 n/2개의 원소를 가진 두 개의 리스트로 분할
• [Conquer] 왼쪽의 리스트와 오른쪽의 리스트를 각각 재귀적으로 합병 정렬
• [Combine] 각각 정렬된 두 개의 리스트를 정렬된 하나의 리스트로 합병하여 리턴

Merge sort

def mergesort (S):

    n = len(S)
    if (n <= 1):
        return S
    else:
        mid = n // 2
        U = mergesort(S[0 : mid])
        V = mergesort(S[mid : n])
        return merge(U, V)

Merge

def merge(U, V):
    S = []
    i = j = 0
    while (i < len(U) and j < len(V)):
        if (U[i] < V[j]):
            S.append(U[i])
            i += 1
        else:
            S.append(V[j])
            j += 1
        if (i < len(U)):
            S += U[i : len(U)]
        else:
            S += V[j : len(V)]
            return S

위 소스코드는 정렬은 됨 하지만 입력리스트인 S 외에 리스트 U 와 V 두개나 더 사용해야 한다.

• 추가적으로 만들어지는 리스트 원소의 총 수
  • merge sort()호출할 때 마다 U랑 V를 새로 생성한다.
  • 전체 재귀 호출 시 원소의 개수 = n + n/2 + n/4 … = 2n

따라서 메모리 사용에 비효율성이 있음,, 이거 어떻게 개선할까?
리스트 더 쓰지 말고 안에서 정렬해보자

Merge sort 2

def mergesort2 (S, low, high):

    if (low < high):

        mid = (low + high) // 2
        mergesort2(S, low, mid)
        mergesort2(S, mid + 1, high)
        merge2(S, low, mid, high)

Merge 2

def merge2 (S, low, mid, high):
    U = []
    i = low
    j = mid + 1
    while (i <= mid and j <= high):
        if (S[i] < S[j]):
            U.append(S[i])
            i += 1
        else:
            U.append(S[j])
            j += 1
    if (i <= mid):
        U += S[i : mid + 1]
    else:
        U += S[j : high + 1]
    for k in range(low, high + 1):
        S[k] = U[k - low]

2.3 분할정복 설계 방법

분할정복 설계 전략

• 분할:문제의 입력사례를 둘 이상의 작은 입력사례로 분할
• 정복:작은 입력사례들을 각각 정복, 작은 입력사례들이 충분히 작지 않으면 재귀 호출
• 통합:필요하면, 작은 입력사례의 해답을 통합하여 원래 입력사례의 해답을 도출

분할정복 알고리즘

• 분할정복 vs 동적계획
  Top-Down vs Bottom-Up
• 분할정복 vs 탐욕법
  탐욕법은 가장 비효율적인 분할정복 알고리즘?
  ex. 교환정렬(greedy)->맨앞 원소와 나머지를 divide했다고 봐도 됨

2.4 퀵 정렬(분활 교환 정렬)

퀵 정렬:Divide-and-Conquer

• 내부(in-place)정렬:추가적인 리스트를 사용하지 않아도 됨
• Quick-Sort
  • [Divide]기준 원소(pivot)를 정해서 기준원소를 기준으로 좌우로 분할
  • [Conquer]왼쪽의 리스트와 오른쪽의 리스트를 각각 재귀적으로 퀵 정렬
  • [Obtain]정렬된 리스트를 리턴

Quick sort

def quicksort (S, low, high):

    if (high > low):

        pivotpoint = partition(S, low, high)
        quicksort(S, low, pivotpoint - 1)
        quicksort(S, pivotpoint + 1, high)

여기서 문제, 어떻게 partition할 것인가??

pivot 정하기

• 편의상 일단 리스트의 첫 원소를 기준원소로 정하자

15를 기준으로 작으면 왼쪽, 크면 오른쪽으로 분할
계속 첫번째 원소를 기준으로 배열을 분할한다

기준 원소로 어떻게 리스트를 나눌까

• 두개의 인덱스 i, j를 이용하서 compare and swap
  

Partition (for Quick Sort)

def partition (S, low, high):

    pivotitem = S[low]
    j = low
    for i in range(low + 1, high + 1):

        if (S[i] < pivotitem):

            j += 1;
            S[i], S[j] = S[j], S[i] # swap

    pivotpoint = j
    S[low], S[pivotpoint] = S[pivotpoint], S[low] # swap
    return pivotpoint

partition()함수를 다르게 구현해볼 수 없을까~~

partition()함수의 다른 구현 방법

S = [26, 5, 37, 1, 61, 11, 59, 15, 48, 19]

[26, 5, 37, 1, 61, 11, 59, 15, 48, 19]: 2, 9

[26, 5, 19, 1, 61, 11, 59, 15, 48, 37]: 4, 7

[26, 5, 19, 1, 15, 11, 59, 61, 48, 37]: 6, 5

[11, 5, 19, 1, 15, 26, 59, 61, 48, 37]

앞 뒤에서 맨 앞 원소인 pivotpoint보다 큰지/작은지 한꺼번에 비교하자
끝난 후 중간에 있는 원소를 pivotpoint로 바꿈

partition2

def partition2 (S, low, high):

    pivotitem = S[low]
    i = low + 1
    j = high
    while (i <= j):

        while (S[i] < pivotitem):

        i += 1

        while (S[j] > pivotitem):

        j -= 1
        
        if (i < j):

            S[i], S[j] = S[j], S[i] # swap

    pivotpoint = j
    S[low], S[pivotpoint] = S[pivotpoint], S[low] # swap
    return pivotpoint

i로 왼쪽부터 pivot item보다 큰 원소가 나올 때 까지 전진
j로 오른쪽부터 pivot item보다 작은 원소가 나올 때 까지 전진
만약 j가 i보다 오른쪽에 있다면 둘을 swap
(왜냐하면 오른쪽에 작은값 왼쪽에 큰 값 둘거니까)

quicksort 2

def quicksort2 (S, low, high):

    if (high > low):

        pivotpoint = partition2(S, low, high)
        quicksort2(S, low, pivotpoint - 1)
        quicksort2(S, pivotpoint + 1, high)