2. Divide and Conquer : Mergesort

본 게시물은 교재 “Algorithms,” Sanjoy Dasgupta(2008)를 참고하여 구현한 알고리즘을 공유하는 게시물입니다.

머리말

지난번 게시물에 이어서 분할정복 알고리즘을 응용하여 2.3절에 해당하는 Mergesort, 합병정렬의 내용을 소개하고 파이썬 코드를 공유하고자 한다.

합병정렬 개념

우선 합병정렬에 대해서 먼저 알아보자.

합병정렬의 경우 하나의 리스트를 반 씩 나누어 재귀적으로 호출하고, 각각 합치는 방식으로 이루어진다.
1. 하나의 전체 리스트를 반 씩 나누어 서브리스트를 형성(재귀적으로 진행)
2. 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 간주하고, 그 리스트를 반환하는 방식으로 이루어진다.

대략적으로 위의 그림에서 설명하는 것처럼 하나의 리스트를 길이가 0 또는 1인 서브리스트로 자른 뒤 정렬하고 합병하는 과정을 거치는 방식이다.

pseudo code

function mergesort(a[1 ... n])
Input: An array of numbers a[1 ... n]
Output: A sorted version of this array
 
if n>1:
	# 길이가 1보다 큰 경우 정렬 후 합병(merge) 과정을 거침 
	return merge(mergesort(a[ 1 ... [n/2]], mergesort(a[[n/2]+1 ... n])
else: 
	#길이가 1보다 작은 경우 이미 정렬된 리스트로 취급하여 합병(merge) 과정을 거치지 않음. 
	return a

function merge(x[1 ... k], y[1 ... l])
	if k=0: # x에 비교할 요소가 없을 때 -> y 전체 반환
    	return y[1 .. l] 
    if l=0: # y에 비교할 요소가 없을 때 -> y 전체 반환
    	return x[1 .. k] 
    
    if x[1] <= y[1]: # 비교 후 재귀적으로 합병할 배열 다시 자르기
    	return x[1] ৹ merge(x[2 ... k] , y[ 1 ... l])
    else:
   		return y[1] ৹ merge(x[2 ... k] , y[ 1 ... l])

위의 코드에서 ৹는 연쇄적인 연산을 의미한다.
이러한 merge의 과정은 재귀 호출에 대해서 상수 시간을 소요한다. 그래서 merge는 선형 연산을 수행하므로
시간 복잡도는 $T[n]=2T(n/2)+O(n)$과 같으며, 빅오로 표기하면 $O(nlogn)$과 같이 표현된다.

python code

def sort(a):
    n=len(a)
    if n==1:  
        return a
    elif n>1:
        return merge(sort(a[0:int(n/2)]),sort(a[int(n/2):n]))

def merge(x,y):
    if len(x)==0: return y
    if len(y)==0: return x

    if x[0]<y[0]: #point 1
        return x[0:1]+merge(x[1:],y)
    else:
        return y[0:1]+merge(x,y[1:])

input=list(map(int,input().split()))
output=sort(input)
for i in output:
    print(i, end=' ')

point 1

처음 수도코드를 보았을 때, 어떻게 연쇄적으로 연산을 이어갈지 고민했다. 새로운 배열을 생성하고 append 혹은 extend 하는 연산을 만들기에는 너무 지저분한 코드가 될 수 있었기 때문에 쉽게 가기 위해서 python의 배열 연산자를 활용하였다. python에서는 "+" 기호로 배열을 붙이는 연산을 할 수 있다.

point 2

배열의 한 가지 요소만을 추출하기 위해서 [0:1]으로 범위를 지정하는 방식을 사용하였다.

---

맺음말

수도코드에서 벗어나는 것이 많이 없었던 알고리즘이라 크게 고민이 됐던 점은 없었지만, 이것 저것 고민할 거리가 있었던 코드이다.

다음에는 2.4절에 해당하는 Medians에 대해 설명하고자 한다.