TIL no.9- 병합 정렬

병합정렬

출처 visualgo.net/sorting

병합 정렬은 Devide and Conquer에 관한 기본 개념이다. 즉 어떤 문제를 우선 작은 문제로 쪼개고 난 후 다시 조합하여 원래의 문제를 푼다는 것이다. 그렇다면 아래의 병합정렬 코드를 풀어서 설명하겠다.

예제 코드

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]
            
            
arr=[23, 11, 45, 36, 15, 67, 33, 21]
print("before", end="")
print(arr)
Qsort(0, 7)
print()
print("after", end="")
print(arr) 

병합 정렬 과정

lt 와 rt는 정렬하고자 하는 양 끝에 배치 시킨다.

mid는 lt와 rt를 더한 후 나눈 정숫값이다.

두 갈래로 뻗어 나가는데 항상 lt는 rt 보다 작다는 조건을 인식해야 한다.

두 수를 비교해서 tmp라는 곳에 임시로 숫자 크기를 비교해 저장해 놓는다.

tmp에 정렬된 숫자를 다시 arr에 복사에 넣는다.

이런 식으로 뻗어 나간 갈래를 타고 올라가서 정렬하는 방법을 병합 정렬이라고 한다.