[알고리즘 일기] 13. 합병 정렬(2)

 

 

문제 13. (2021-05-13)

 

합병 정렬 구현하기

Divide and Conquer 방식으로 merge_sort 함수를 써 보세요. merge_sort는 파라미터로 리스트 하나를 받고, 정렬된 새로운 리스트를 리턴합니다.

 

 

❧ 테스트 셋

def merge(list1, list2):
    merge_list = []
    i = 0
    j = 0
    
    while i < len(list1) and j < len(list2):
        if(list1[i] < list2[j]):
            merge_list.append(list1[i])
            i+=1
        else:
            merge_list.append(list2[j])
            j+=1
    if (i == len(list1)):
        return merge_list + list2[j:]
    else:
        return merge_list + list1[i:]
    return merge_list

def merge_sort(my_list):
    #Code

# Test
print(merge_sort([1, 3, 5, 7, 9, 11, 13, 11]))
print(merge_sort([28, 13, 9, 30, 1, 48, 5, 7, 15]))
print(merge_sort([2, 5, 6, 7, 1, 2, 4, 7, 10, 11, 4, 15, 13, 1, 6, 4]))

 

❧ 출력 예시

[1, 3, 5, 7, 9, 11, 11, 13]
[1, 5, 7, 9, 13, 15, 28, 30, 48]
[1, 1, 2, 2, 4, 4, 4, 5, 6, 6, 7, 7, 10, 11, 13, 15]

 

---

❧ 정답

def merge(list1, list2):
    merge_list = []
    i = 0
    j = 0
    
    while i < len(list1) and j < len(list2):
        if(list1[i] < list2[j]):
            merge_list.append(list1[i])
            i+=1
        else:
            merge_list.append(list2[j])
            j+=1
    if (i == len(list1)):
        return merge_list + list2[j:]
    else:
        return merge_list + list1[i:]
    return merge_list

# 리스트를 반으로 나눔
def merge_sort(my_list):
    # base case
    if len(my_list) < 2:
        return my_list
    else:
        list1 = my_list[:(len(my_list))//2]
        list2 = my_list[(len(my_list))//2:]
        # 재귀 호출을 통한 분할 정복
        return merge(merge_sort(list1), merge_sort(list2))

print(merge_sort([1, 3, 5, 7, 9, 11, 13, 11]))
print(merge_sort([28, 13, 9, 30, 1, 48, 5, 7, 15]))
print(merge_sort([2, 5, 6, 7, 1, 2, 4, 7, 10, 11, 4, 15, 13, 1, 6, 4]))

 

1️⃣ Divide: 리스트 슬라이싱을 통해 리스트를 반씩 나눈다.

2️⃣ Conquer: 왼쪽 반과 오른쪽 반을 각각 merge_sort 함수로 정렬한다.

3️⃣ Combine: 정렬된 두 리스트를 merge 함수로 합친다.

 

728x90