[김태원 알고리즘] 병합정렬 (후위순회)

사용 언어: Python3

문제

병합정렬을 구현해보자!

풀이

def mergeSort(lt, rt):
    if lt < rt:
        mid = (lt + rt) // 2
        mergeSort(lt, mid)
        mergeSort(mid+1, rt)
        # 병합정렬은 후위순회 (본연의 일을 맨 마지막에)
        p1, p2 = lt, 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 += arr[p1:mid+1]
        else:
            tmp += arr[p2:rt+1]
        # arr에 복사
        for i in range(len(tmp)):
            arr[i+lt] = tmp[i] # arr 인덱스 주의

arr = [23, 11, 45, 36, 15, 67, 33, 21]
print('Before sort : ', end=' ')
print(arr)

mergeSort(0,7)
print()

print('After sort : ', end=' ')
print(arr)

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기