병합정렬

병합정렬은 ‘분할 정복’ 방법을 채택한 알고리즘이다. 병합정렬의 시간복잡도는 O(N * logN)을 가진다.

예시 : 7 6 5 8 3 5 9 1 을 오름차순으로 정렬하는 프로그램을 작성하시오.

병합 정렬 은 하나의 큰 문제를 두개의 작은 문제로 분할한 뒤에 각자 계산하고 나중에 합치는 방법을 이용한다. 즉 반으로 나누고 나중에 정렬한다는 것이다.

  • 시작단계 : 모든 요소를 계속 반으로 나누어 결국엔 1개요소만 1칸에 존재한다.

| 7 | 6 | 5 | 8 | 3 | 5 | 9 | 1 | | :–: | :–: | :–: | :–: | :–: | :–: | :–: | :–: |

  • 1단계

| 6 7 | 5 8 | 3 5 | 1 9 | | :—-: | :—-: | :—-: | :—-: |

  • 2단계

| 5 6 7 8 | 1 3 5 9 | | :————-: | :———————: |

  • 3단계

| 1 3 5 5 6 7 8 9 |
| :———————————-: |

위를 보면 합치는 순간에 정렬을 수행한다.

1단계에서 2단계로 병합하는부분을 본다면

i   j  
6 7 5 8
k      
5      

i 와 j를 우선 비교하여 작은 수를 k에 위치시키고

j 를 우측으로 한칸 이동시킨다.

i     j
6 7   8
  k    
5      

이후 다시 i 와 j를 비교하여 더 작은 i값인 6을 k f로 위치시킨다.

이와 같은 과정을 반복하여 정렬을 완성한다. 총 4번만 반복하면 정렬이 완성된다.

  • 완성된 정렬
  i   j
       
      k
5 6 7 8

파이썬으로 구현

def merge_sort(array):
    if len(array)<=1:   # 길이가 1이면 나누지않고 반환
        return array

    mid = len(array)//2
    left = merge_sort(array[:mid])  # mid를 기준으로 왼쪽 배열 계속 분할
    right = merge_sort(array[mid:])  # mid를 기준으로 오른쪽 배열 계속 분할

    i,j,k = 0,0,0

    # 분할된 배열끼리 비교
    while i<len(left) and j<len(right):
        if left[i]<right[j]:
            array[k] = left[i]
            i += 1
        else:
            array[k] = right[j]
            j += 1
        k += 1  # 배열 추가되면 k 1증가
    
    # i 나 j중 한쪽이 모두 k에 추가되었을때
    if i == len(left):
        while j < len(right):
            array[k] = right[j]
            j += 1
            k += 1
    elif j == len(right):
        while i < len(right):
            array[k] = lefg[i]
            i += 1
            k += 1
    return array

병합정렬을 이용하여

List = [7, 6, 5, 8, 3, 5, 9, 1] 을 정렬해보자

def merge_sort(array):
    if len(array)<=1:   # 길이가 1이면 나누지않고 반환
        return array

    mid = len(array)//2
    left = merge_sort(array[:mid])  # mid를 기준으로 왼쪽 배열 계속 분할
    right = merge_sort(array[mid:])  # mid를 기준으로 오른쪽 배열 계속 분할

    i,j,k = 0,0,0

    # 분할된 배열끼리 비교
    while i<len(left) and j<len(right):
        if left[i]<right[j]:
            array[k] = left[i]
            i += 1
        else:
            array[k] = right[j]
            j += 1
        k += 1  # 배열 추가되면 k 1증가
    
    # i 나 j중 한쪽이 모두 k에 추가되었을때
    if i == len(left):
        while j < len(right):
            array[k] = right[j]
            j += 1
            k += 1
    elif j == len(right):
        while i < len(right):
            array[k] = left[i]
            i += 1
            k += 1
    return array

num = [7, 6, 5, 8, 3, 5, 9, 1]

print('주어진 list num = ', num)

print('병합정렬 실행 : ', merge_sort(num))

주어진 list num =  [7, 6, 5, 8, 3, 5, 9, 1]
병합정렬 실행 :  [1, 3, 5, 5, 6, 7, 8, 9]