Algorithm - 병합 정렬(선수지식)

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

선수지식(algorithm)

간단한 예제를 통해 병합 정렬의 원리를 이해하고자 한다.

 

 

---

 

예시(Python)

답안

def Dsort(lt, rt):
    if lt < rt:
        mid = (lt + rt) // 2
        Dsort(lt, mid)
        Dsort(mid + 1, rt)
        p1 = lt
        p2 = mid + 1
        tmp = []
        while p1 <= mid and p2 <= rt:
            if arr[p1] < arr[p2]:
                tmp.append(arr[p1])
                p1 += 1
            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]    

if __name__ == "__main__":
    arr = [23, 11, 45, 36, 15, 67, 33, 21]
    print("Before sort : ", end='')
    print(arr)
    Dsort(0, 7)
    print()
    print("After sort : ", end='')
    print(arr)

 

출력

Before sort : [23, 11, 45, 36, 15, 67, 33, 21]

After sort : [11, 15, 21, 23, 33, 36, 45, 67]

 

 

중요내용

1. 병합 정렬은 후위순회(왼쪽 자식노드 -> 오른쪽 자식노드 -> 부모노드) 방식으로 진행된다.
2. 부모노드에서는 2개의 간선으로 왼쪽 자식노드와 오른쪽 자식노드로 분할된다.
3. 참고로, 왼쪽 자식노드는 (lt, lt+rt // 2)의 값을 가지며 오른쪽 자식노드는 (lt+rt//2 + 1, rt)의 값을 가진다.
4. 단, 부모노드에서 자식노드로 분할되는 것은 lt < rt 조건에서만 이루어진다. (if절의 조건)
5. 변수 p1과 p2는 왼쪽 자식노드와 오른쪽 자식노드의 리스트가 각자 정렬을 마친 후, 부모 노드에서 두 리스트를 병합하여 정렬할 때 사용되는 리스트 인덱스 번호이다.
6. while문의 원리는 "두 리스트 합치기" 문제에서 사용했던 원리와 동일하다.
7. 리스트 tmp는 특정 노드에서 해당 리스트의 벨류를 정렬시킬 때 사용되는 임시 저장공간이다.
8. 리스트 tmp를 사용하여 리스트 정렬이 완료되면, 해당 결과를 리스트 arr에 그대로 반영해줘야 한다.