본문 바로가기

하루 30분 알고리즘 기초다지기

[python] merge sort 알고리즘 Divide&Conquer 분할정복 알고리즘 으로 해결하기

Merge Sort(합병 정렬)

Merge sort는 분할 정복을 통해 문제를 해결하는 정렬방식이다. 방식을 자세히 설명하자면 아래와 같다. 

 

Divide :

  • 배열을 각각 n/2개의 데이터로 만들어진 두개의 부분배열로 분할한다. 

Conquer : 

  • 나누어진 부분배열에 대하여 재귀적으로 합병 정렬을 수행한다. 
  • 단, 데이터의 개수가 1개인 경우에는 그 자체로 정렬된 상태이다. 

Combine(Merge):

  • 두개의 이미 정렬된 부분 배열을 통합하여 n개의 정렬된 배열로 만든다. 

 

 

merge sorting은 분할하고 합치는 과정에서 새로운 배열을 필요로 하기 때문에In-place하지 않지만, stable한 sorting 알고리즘이다. 

시간복잡도는 O(nlogn)으로 좋은 알고리즘이지만, 앞서 말했듯이 In-place하지 않다는 문제점이 있다. 

 

merge sort의  Top-Down과 Bottom-UP

merge sort은 Top-Down 부분과 Bottom-UP 부분으로 나눠서 볼수 있는데 설명하면 다음과 같다. 

 

Top-Down : 분할하는 과정에서 계속 작은 구간으로 분할해 나간다. 

Bottom-UP : 정렬된 작은 구간을 Merge하여 정렬된 큰 구간을 만드는 과정이다. 

이 Bottom-UP과정을 반복해 실행하면서 merge sort가 진행된다. 

 

 

Merge하는 방법

merge sorting의 핵심인 merge하는 부분을 살펴보자.

 

분할된 두배열의 가장 작은 값끼리 비교하는 것을 알 수 있다. 가장 작은값 부터 순서대로 비교하며 새로운 배열에 값을 쌓아간다. best-case는 merge 할 두 배열이 큰 값 작은 값으로 잘 분류되어 있는 것이다. 

 

 

코드 구현

그럼 merge sort를 코드로 구현해 보자.  

 

 

merge sort를 코드로 구현하면 아래와 같이 두 가지 부분으로 나타낼 수 있다. 하나는 분할하는 부분이고 하나는 병합하는 부분이다. 

merge sort를 분할하는 방법은 재귀와 반복 두가지 방법으로 구현할 수 있다. 먼저 재귀방법이다.

  • 재귀
# divide recursive
def mergeSort(array, low, high):

    # low가 high보다 작을 때만 진행 
    if low < high : 
        mid = (low+high)//2
        mergeSort(array, low, mid)
        mergeSort(array, mid+1, high)
        merge(array, low, mid, high)

 

  • 반복
#divide iterate
def mergeSort(array):
    n = len(array)
    # 비교 횟수 계산할 counter
    size = 1
    # 사이즈가 배열의 크기 n 보자 작을 때만 실행
    # 배열을 1, 2, 4, 8.... 이런식으로 구간을 나눔
    while size < n:
        for low in range(0, n, 2 * size):
            # 배열 index를 넘어가지 않기 위해서 min을 사용
            mid = min(low + size - 1, n - 1) 
            high = min(low + 2 * size - 1, n - 1)
            merge(array, low, mid, high)
        size *= 2
    return counter[0]

 

 

나누었던 두 배열을 합치는 부분을 아래와 같이 구현할 수 있다. 

# combine
def merge(array, low, mid, high):
    i = k = low
    j = mid+1
    tmp = array[:]

    # 값 비교하기 
    while i<=mid and j<=high:
        if tmp[i] <= tmp[j]:
            array[k] = tmp[i]
            i += 1
        else : 
            array[k] = tmp[j]
            j += 1
        k+=1
    
    # 남은 값이 있다면 모두 넣기 
    while i<=mid:
        array[k]=tmp[i]
        i+=1
        k+=1
    while j<=high:
        array[k]=tmp[j]
        j+=1
        k+=1