이분검색과 합병정렬

    이분검색(binary search)

분할정복(Divide-and-Conquer)

 

문제 : 정렬된 리스트 S에 어떤 키 x가 존재하는가?

해답 : 존재하면 x의 위치, 없다면 -1을 리턴

 

 

알고리즘

 

S의 정가운데 원소와 x를 비교하여 같으면 해당 위치를 리턴, 없다면

1. 정가운데 원소를 기준으로 S를 두개의 리스트로 분할

2. x가 정가운데 원소보다 크면 오른쪽, 작으면 왼쪽을 재귀호출

3. 선택한 리스트에서 얻은 답을 리턴

 

# Binary Search (Recursive)

def location(S, low, high):
	if (low > high):
    	return 0
    else:
    	mid = (low + high) // 2
        print(low, mid, high)
        if (x == S[mid]):
        	return mid
        elif (x < S[mid]):
        	return location(S, low, mid-1)
        else:  # x > S[mid]:
        	return location(S, mid+1, high)
           
# 0번째 원소는 세지 X
S = [-1, 10, 12, 13, 14, 18, 20, 25, 27, 30, 35, 40, 45]
x = 18
loc = location(S, 1, len(S))
print('S =', S)
print('x =', x)
print('loc =', loc)

 

    합병 정렬

: 두개의 리스트로 나눠서 정렬하고, merge시켜준다. 

 

리스트(배열)의 정렬문제

문제 : 정렬되지 않은 리스트 S를 오름차순으로 정렬하시오.

해답 : 정렬된 리스트를 반환

 

알고리즘

 

1. 원소가 n개인 S를 n/2개의 원소를 가진 두개의 리스트로 분할한다.

2. 왼쪽 리스트와 오른쪽 리스트를 각각 재귀적으로 합병 정렬

3. 정렬된 두개의 리스트를 정렬된 하나의 리스트로 합병하여 리턴한다. 

 

 

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[i])
        	j += 1
    if (i < len(U)):
    	S += U[i:len(U)]
    else:
    	S += V[i:len(V)]
    return S
    
# 실행
S = [27, 10,12, 20, 25, 13, 15, 22]
print('Before: ', S)
X = mergeSort(S)
print('After: ', X)

 

-> 입력리스트 S이외에 리스트 U와 V를 추가사용하므로 메모리가 비효율적으로 사용된다.

 

 

 

* Enhanced Merge Sort

 

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 <= mid):
    	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]

S = [27, 10, 12, 20, 25, 13, 15, 22]
print('Before: ', S)
mergeSort2(S, 0, len(S)-1)
print('After: ', S)