[알고리즘 일기] 12. 합병 정렬(1)

 

 

문제 12. (2021-05-12)

합병 정렬

합병 정렬 알고리즘 중 사용되는 merge 함수를 작성하시오.

 

 

주의사항

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

 

 

❧ 테스트 셋

def merge(list1, list2):
    # Code
    
# Test
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]))

 

❧ 출력 예시

[1]
[1]
[1, 2]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 3, 4, 6, 7, 8, 9, 10]

 

---

❧ 정답

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
    
# 테스트
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]))

 

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

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

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

 

728x90