병합정렬 오류 해결

https://knowledgeforengineers.tistory.com/22

병합정렬 예제

 

전에 병합정렬 예제를 올렸었다. 당시 내가 스스로 작성했던 소스코드가 이랬었다.

 

def mergesort(lst):
    l = int(len(lst)/2 - len(lst)%2)
    lst1 = lst[:l]
    lst2 = lst[l:]
    if l>1:
        mergesort(lst1)
        mergesort(lst2)
    return mergesort_sub(lst1, lst2)


# 병합하는 모듈
def mergesort_sub(lst1, lst2):
    new_lst = []
    n1 = len(lst1)
    n2 = len(lst2)
    i = 0
    j = 0
    while n1>0 and n2>0:
        if lst1[i] > lst2[j]:
            new_lst.append(lst2[j])
            j += 1
            n2 -= 1
        else:
            new_lst.append(lst1[i])
            i += 1
            n1 -= 1
    if n1>0:
        while n1>0:
            new_lst.append(lst1[i])
            i += 1
            n1 -= 1
    if n2>0:
        while n2>0:
            new_lst.append(lst2[j])
            j += 1
            n2 -= 1
    return new_lst

a = [1,3,5,8,9]
b = [2,4,6,7,10]
print(mergesort_sub(a,b))
d = [6,8,3,9,10,1,2,4,7,5]
print(mergesort(d))

병합 모듈에는 문제가 없었다. 문제점은

1. 중단점을 찾는 조건이 'l'이라는 점과(리스트의 원소의 개수가 1개일 때로 설정해야만 한다.)

2. 엉뚱하게도 mergesort의 파라미터로 리턴값을 사용하는 것이 아니라, 단순히 lst를 두개로 나눈 리스트인 lst1, lst2를 그대로 mergesort 함수에 넣었다는 점이다. 

 

이를 아래와 같이 수정해 문제를 해결하였다.

 

def mergesort(lst):
	#분할부
    n = len(lst)
    if n <= 1:
        return lst
    l = n // 2
    lst1 = mergesort(lst[:l])
    lst2 = mergesort(lst[l:])
    # 병합부
    new_lst = []
    n1 = len(lst1)
    n2 = len(lst2)
    i = 0
    j = 0
    while n1>0 and n2>0:
        if lst1[i] > lst2[j]:
            new_lst.append(lst2[j])
            j += 1
            n2 -= 1
        else:
            new_lst.append(lst1[i])
            i += 1
            n1 -= 1
    if n1>0:
        while n1>0:
            new_lst.append(lst1[i])
            i += 1
            n1 -= 1
    if n2>0:
        while n2>0:
            new_lst.append(lst2[j])
            j += 1
            n2 -= 1
    return new_lst

d = [6,8,3,9,10,1,2,4,7,5]
print(mergesort(d))