[파이썬] 합병정렬 (1) merge 함수 - 분할정복 ★

실습 설명

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

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

실습 결과

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]))

[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]

 

오답 1

• 주어진 list가 0인 경우를 고려하지 못함
• `+=` 연산의 경우 두 list를 합쳐서 새로운 list를 만드는 것이니, 당연히 느리다.
• 그런데 `append`의 경우 하나의 list에다가 항목을 추가하는 것이니, 당연히 += 연산을 이용하는 것보다 빠르다.

def merge(list1, list2):
    # 여기에 코드를 작성하세요
    merged_list = []
    i = 0
    j = 0
    
    while len(merged_list) < ( len(list1) + len(list2) ) :
        
        if (list1[i] < list2[j]) or len(list2) == 0 : 
            merged_list.append(list1[i])
            i += 1
        elif (list1[i] > list2[j]) or len(list1) == 0 :
            merged_list.append(list2[j])
            j += 1
    
    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]))

Traceback (most recent call last):
  File "main.py", line 19, in <module>
    print(merge([1],[]))
  File "main.py", line 9, in merge
    if (list1[i] < list2[j]) or len(list2) == 0 : 
IndexError: list index out of range