Merge Sort

# Merge Sort

합병정렬은 하나의 리스트를 두개의 균등한 크기의 리스트로 분할하고 분할된 부분 리스트를 합치면서 정렬하여 전체가 정렬되게 하는 방법입니다.

리스트 분할은 각 서브리스트의 크기가 1이 될 때까지 진행합니다.

이 분할된 리스트들을 합치면서 정렬해야하는데, 합칠때도 균등한 크기로 합치면서 정렬하게 됩니다

 

[ 시간복잡도 ] 

분할 과정은 한번 분할 할때마다 리스트의 크기가 1/2씩 감소를 하게 됩니다. 그래서 총 N개의 데이터를 분할을 한다고 하면 N/2개의 서브리스트 2개를 얻고, 또 분할하면 N/4개의 서브리스트 4개를 얻게 되는데 이 과정을 서브리스트의 크기가 1이 될때까지 반복을 하면 밑이 2인 logN의 시간복잡도를 가지게 됩니다. 분할 후 리스트들을 합치는 과정에서, 각 element들을 비교하면서 정렬하기 때문에 데이터 N개 만큼의 시간복잡도를 추가적으로 가지게 됩니다.

그래서 merge sort의 시간복잡도는 O(NlogN)이 됩니다

[ 분할 정복 알고리즘 ] 

합병정렬과 같이 하나의 문제를 동일한 유형의 작은 문제들로 분할하고, 작은 문제들의 결과를 조합하여 큰 문제를 해결하는 방식의 알고리즘을 분할 정복 알고리즘(Divide and Conquer Algorism)이라고 합니다. 분할 정복 알고리즘은 보통 재귀함수로 구현된다는 특징이 있습니다

 

 

# 코드 구현(Python)

merge sort는 배열을 분할한 후에 다시 합병하는 과정을 거쳐야하므로 두개를 나눠서 설명하도록 하겠습니다.

[ Divide ] 

def MergeSort(arr):
    if len(arr)<= 1:
        return
    mid = len(arr)//2
    left = arr[:mid]
    right = arr[mid:]
    MergeSort(left)
    MergeSort(right)

if len(arr)<= 1:
        return
mid = len(arr)//2        배열을 절반씩 분할하므로 중앙 값을 찾아야 합니다
left = arr[:mid]           중앙을 기준으로 왼쪽과,
right = arr[mid:]         오른쪽으로 배열을 나눠 줍니다. 이렇게 하면 왼쪽 오른쪽 동일한 크기의 인덱스가 나옵니다
MergeSort(left)
MergeSort(right)        재귀함수를 통해 배열을 계속해서 분할해줍니다. 이때 재귀함수가 무한하게 호출될 위험이 있으므로 종료조건을 걸어주어야하는데, 이는 위의 if문을 통해 배열의 크기가 1일때 종료되도록 종료조건을 걸어주었습니다.

이렇게 merge sort를 다 돌고 나면 mid, left, right에는 분할된 인덱스가 존재할 것입니다. 이는 우리가 구현함에 있어 arr를 직접 나눠서 수많은 배열로 만드는 것이 아니라, arr가 둘씩 분할되는 인덱스의 위치를 찾는 작업이라고 할 수 있습니다.

[ Conquer ]

    l = 0
    r = 0
    idx = 0
    while l<len(left) and r<len(right):
        if left[l] <= right[r]:
            arr[idx] = left[l]
            l += 1
        else:
            arr[idx] = right[r]
            r += 1
        idx += 1
    while l<len(left):
        arr[idx] = left[l]
        l += 1
        idx += 1
    while r<len(right):
        arr[idx] = right[r]
        r += 1
        idx += 1

l = 0         분할된 왼쪽 리스트의 시작 인덱스
r = 0        분할된 오른쪽 리스트의 시작 인덱스
idx = 0     원본 배열의 인덱스
while l<len(left) and r<len(right):   left나 right중에 하나라도 리스트에 있는 값을 모두 꺼내게 되면 while문은 종료됩니다.
    if left[l] <= right[r]:      if-else문을 통해 왼쪽과 오른쪽리스트의 값을 비교해서 위치를 이동시켜줍니다.
        arr[idx] = left[l]     
        l += 1                     
    else:                          
        arr[idx] = right[r]  
        r += 1                     
    idx += 1        if문이 종료되면 idx + 1

위의 while문을 통해 left나 right중 하나라도 리스트에 있는 값을 모두 꺼내게 되어 while문이 종료되면, 아직 left나 right에 값이 남아있을 수 있습니다. 따라서 아래 while문을 통해 리스트에 남은 값들을 모두 위치이동시켜주게 됩니다

while l<len(left):           왼쪽 리스트에 값이 남는 경우
    arr[idx] = left[l]  
     l += 1                 
    idx += 1              
while r<len(right):       오른쪽 리스트에 값이 남는 경우
    arr[idx] = right[r]
    r += 1                  
    idx += 1

 

[ Test Code ]

if __name__ == '__main__':
    arr = [9,1,6,3,7,2,8,4,5,0]
    MergeSort(arr)
    print(arr)
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

 

# 전체 코드

깃허브에서 테스트 코드를 포함한 전체 코드를 보실 수 있습니다.

GitHub - sonzwon/TIL: Today I Learned