merge sort | 합병정렬

해당 글은 python3을 기준으로 작성하였다.

출처 : https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC

merge sort는 divide and conquer 방법을 사용한 정렬.

 

 

divide and conquer

비유를 해보자.

 

A회사는 하나의 큰 프로젝트를 반으로 쪼갠 후, B, C 두 회사에 하청을 맡겼다.

 

그리고 B,C 회사는 하청받은 프로젝트를 또 반으로 쪼개 

 

B는 D, E회사에 C는 F,G 회사에 하청을 맡겼다.

 

D와 E는 프로젝트를 끝내 B에 보내고, F와 G도 결과물을 C에 보냈다.

 

B와 C는 하청업체로부터 받은 결과물을 합쳐 A로 보냈다.

 

A는 B와 C로부터 받은 결과물을 합쳐 큰 프로젝트를 완수했다.

 

merge sort는 다음과 같이 작동한다.

 

1. 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
2. 분할(divide) : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
3. 정복(conquer) : 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
4. 결합(combine) : 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 이때 정렬 결과가 임시배열에 저장된다.
5. 복사(copy) : 임시 배열에 저장된 결과를 원래 배열에 복사한다.

(출처 : 위키피디아 '합병정렬')

 

1. 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다.

당연하니 넘어간다.

 

2. 분할(divide) 

python3 기준으로 하나의 list를 반으로 쪼개주면 된다.

대충 다음과 같이 하면 되겠다.

mylist = [3,5,7,9,8,6]

mid = len(mylist)//2

left_list = mylist[:mid]
right_list = mylist[mid:]

 

3,4. 정복(conquer), 결합(combine)

따로 설명하기 어려워서 합쳐서 설명하겠다.

분할에서 나눴던 두개의 리스트를 하나로 합쳐줘야 한다.

합치는 과정에서 정렬도 해줘야 한다.

 

정렬된 두 리스트 [5,7]과 [3,9]가 있다.

이 두 리스트를 결합을 하는 과정은 다음과 같다. 

5	7		3	9
5	7		9			3
7			9			3	5
			9			3	5	7
						3	5	7	9

 

한 쪽에 값이 많이 남아있으면 결과 리스트에 한번에 붙혀주면 된다.

3	4		5	6
	4		5	6		3
			5	6		3	4
						3	4	5	6

 

 

Code

---

정렬된 두개의 리스트를 하나로 합병하는 함수

def merge(list1, list2):
    result = []
    while len(list1)>0 and len(list2)>0:
        if list1[0] < list2[0]:
            result.append(list1.pop(0))
        else:
            result.append(list2.pop(0))
    
    if len(list1)>0:
        return result + list1
    else:
        return result + list2

 

merge sort

def merge_sort(my_list):
    if len(my_list)>1:
        mid = len(my_list)//2
        return merge(my_list[:mid],my_list[mid:])
    return my_list # 작동순서 1번에 해당