이분 검색

이분 검색 : 분할 정복
문제 : 정렬된 리스트 S에 어떤 키 x가 존재하는가?
해답 : 존재하면 S에서 x의 위치, 아니면 -1을 리턴

분할정복

• s의 정가운데 원소와 x를 비교하여 같으면 해당 위치를 리턴, 아니면 :
• [Divide] 정가운데 원소를 기준으로 S를 두 개의 리스트로 분할
• [Conquer] x가 정가운데 원소보다 크면 오른쪽, 작으면 왼쪽을 재귀 호출
• [Obtain] 선택한 리스트에서 얻은 답을 리턴

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)

합병 정렬

문제 : 정렬되지 않은 리스트 S를 오름차순으로 정렬하시오
해답 : 정렬된 리스트 S'를 리턴

분할정복

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

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)
        
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
    

mergesort2 : U,V 라는 별도의 메모리를 사용하지 않는 방법

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)

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[i])
            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]