병합정렬 (merge-sort) _ 후위순회방식의 DFS

병합정렬이 어떻게 이루어지는지를 배웠다. 그 과정에 핵심적으로 작용하는 건 후위순회방식의 DFS였다.

후위순회방식은 언제 쓰이는가 생각해보면,

즉, 각 레벨에서 동일한 패턴의 작업을 해야 해서 재귀를 불러야 하되,

나보다 자식(?)/아래 레벨의 아이들이 먼저 작업을 완료해줘야, 이를 토대로 나의 본연의 일을 할 수 있는 경우.

병합정렬이 이 경우에 해당한다.

왜냐하면 병합정렬은 자신의 왼쪽 오른쪽 아이들이 정렬된 상태로 있어야, 그 양쪽을 합칠 수 있기 때문이다.

즉 더 이상 양쪽으로 쪼갤 수 없을 레벨 (2칸짜리 배열) 까지 깊이 들어가서, 그 친구들이 정렬을 마친 후에야

상위 레벨로 돌아와서, 자식들이 배열을 마쳤다는 안심스러운 토대위에서 자기 레벨에서의 정렬을 진행할 수 있다.

 

1. 손으로 배운내용 정리

2. 코드

arr = [23, 11, 45, 7, 15, 67, 33, 21]

def Dsort(lt, rt):
    if lt < rt:
        mid = (lt + rt) // 2

        # 나의 왼/오 조각들이 먼저 정렬 처리를 해와야 하므로
        # 재귀적 호출을 먼저하고 완료되길 기다린다.
        Dsort(lt, mid)
        Dsort(mid+1, rt)

        # 왼/오 자식 조각들이 완료한 작업을 바탕으로
        # 이제 나의 레벨에서의 본연의 작업을 한다.
        p1 = lt
        p2 = mid+1
        tmp = []  # 내 레벨에서 정렬한 결과물을 담아두고, 이후 arr 에 복사하기 위한 리스트
        while p1 <= mid and p2 <= rt:  # p1이나 p2중 어느 하나가 자신의 구역을 다 훑으면 종료
            # 왼쪽에서 제일 작은애랑 오른쪽에서 제일 작은애가 비교해서, 그 중 더 작은애를 tmp 에 먼저 append.
            if arr[p1] < arr[p2]:
                tmp.append(arr[p1])
                p1 += 1  # tmp 에 붙였으니 포인터 한칸 전진

            else:
                tmp.append(arr[p2])
                p2 += 1

        if p1 <= mid:
            tmp = tmp + arr[p1:mid+1]
        if p2 <= rt:
            tmp = tmp + arr[p2:rt+1]
        for i in range(len(tmp)):
            arr[lt+i] = tmp[i]

Dsort(0, 7)
print(arr)