[알고리즘] 합병정렬 : merge 함수 작성

합병정렬에서의 Divide and Conquer

1. Divide 리스트를 반으로 나눈다.

2. Conquer 왼쪽 리스트와 오른쪽 리스트를 각각 정렬한다.

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

 

실습설명

합병 정렬 알고리즘 중 사용되는 merge 함수를 작성해 보세요.

merge 함수는 정렬된 두 리스트 list1과 list2를 받아서, 하나의 정렬된 리스트를 리턴합니다.

 

 

해설

힌트1

merge 함수는 정렬된 두 리스트 list1과 list2를 파라미터로 받고, 합쳐진 리스트(merged_list)를 리턴해주는데, 처음에는 merged_list를 빈 리스트로 정의한다.

merged_list = []

list1과 list2는 이미 정렬되어 있기 때문에, merged_list에 먼저 추가될 원소는 두 리스트의 왼쪽 값 중 더 작은 값이다.list1과 list2의 원소들을 차례로 비교하여, merged_list에 작은순서대로 추가하면 된다.

 

힌트2

step      i           j        list1[i] list2[j]                              동작                                                  merged_list      

1	0	0	2	1	merged_list.append(list2[j]) j += 1	[1]
2	0	1	2	3	merged_list.append(list1[i]) i += 1	[1, 2]
3	1	1	9	3	merged_list.append(list2[j]) j += 1	[1, 2, 3]
4	1	2	9	5	merged_list.append(list2[j]) j += 1	[1, 2, 3, 5]
5	1	3	9		merged_list += list1[i:]	[1, 2, 3, 5, 9, 10]

 

힌트3

이에 맞게 코드를 작성해보면

def merge(list1, list2):
    # 정렬된 항목들을 담을 리스트
    merged_list = []

    i = 0
    j = 0

    # list1과 list2를 돌면서 merged_list에 추가
    while i < len(list1) and j < len(list2):
        if list1[i] > list2[j]:
            merged_list.append(list2[j])
            j += 1
        else:
            merged_list.append(list1[i])
            i += 1

보다시피 두 리스트중 하나만 소진되어도 while문은 종료된다. 소진되지 않은 리스트에 대한 처리는 step5에서 하는데, step5에 대한 코드는 어떻게 작성할까.

 

힌트4

우선 list1과 list2 두리스트중 소진된 리스트와 소진되지 않은 리스트가 각각 무엇인지 판별해야한다. 어떻게 할 수 있을까?

 

힌트5

i와 j를 확인해주면 된다. i가 len(list1)과 같다면 list1이 소진된 것이고, j가 len(list2)와 같다면 list2가 소진 된것이다.

소진되지 않은 리스트에 남은 항목들을 merged_list에 추가시켜 주면된다.

 

 

답안

def merge(list1, list2):
    i = 0
    j = 0

    # 정렬된 항목들을 담을 리스트
    merged_list = []

    # list1과 list2를 돌면서 merged_list에 항목 정렬
    while i < len(list1) and j < len(list2):
        if list1[i] > list2[j]:
            merged_list.append(list2[j])
            j += 1
        else:
            merged_list.append(list1[i])
            i += 1

    # list2에 남은 항목이 있으면 정렬 리스트에 추가
    if i == len(list1):
        merged_list += list2[j:]

    # list1에 남은 항목이 있으면 정렬 리스트에 추가
    elif j == len(list2):
        merged_list += list1[i:]

    return merged_list

# 테스트 코드
print(merge([1],[]))
print(merge([],[1]))
print(merge([2],[1]))
print(merge([1, 2, 3, 4],[5, 6, 7, 8]))
print(merge([5, 6, 7, 8],[1, 2, 3, 4]))
print(merge([4, 7, 8, 9],[1, 3, 6, 10]))