병합정렬

Merge Sort

Shell 정렬은 보통의 삽입정렬을 리스트를 쪼개는 방식으로 성능을 향상시킨 예이다. 이러한 분할정복방식을 검색에 도입한 알고리듬이 여럿 있는데, 병합정렬(merge sort)도 그 중 하나이다. 병합정렬은 리스트를 재귀적으로 절반으로 나누어 처리하는 방식이다. 만약 리스트가 비어있거나 원소가 하나만 있다면 그 자체로 정렬되어 있다고 보고, 그것이 베이스 케이스1가 된다.

만약 2개 이상의 원소가 있다고하면 병합정렬은 이 리스트를 반으로 쪼개어 각각을 병합정렬을 적용한다. 각각의 반쪽이 정렬되면 “병합”으로 불리는 과정이 수행된다. 병합은 정렬된 두 개의 리스트를 하나의 정렬된 리스트로 합치는 과정이다.

쪼개진 부분 리스트를 합치는 방법은 다음과 같다.

  1. 일단 쪼개진 부분리스트들은 ‘정렬된 상태에 있다’고 본다. 이 두 부분 리스트는 기본적으로 원래 리스트의 왼쪽, 오른쪽 절반 (홀수인 경우 우측 절반이 한 개 더 가져감)으로 되어 있었을 것이다.
  2. 왼쪽과 오른쪽 부분 집합의 첫 원소를 비교하여 작은 것을 원본리스트의 첫 원소로 취한다. 원소를 빼낸 부분 집합에서서는 인덱스를 다음으로 옮긴다.
  3. 다시 2를 반복한다.
  4. 만약 한쪽 부분 집합의 원소가 모두 제거되었으면, 나머지 반쪽의 원소를 순서대로 모두 취한다.

이 과정을 한 번 추적해보자.

[45][53][26][93][62][20][33][17]
^^^^^^^^^^^^^^^^

절반을 잘라 왼쪽/오른쪽으로 나눈다음, 각각의 절반을 다시 병합정렬한다. 그래서 각 절반이 병합 정렬되었다고 가정해보자.

[26][45][53][93] + [17][20][33][62]
 ^^                 ^^
[  ][  ][  ][  ][  ][  ][  ][  ]

각 부분집합의 head 중에서 작은 것을 원래 리스트에 넣는다. (원래 리스트에는 이미 값이 들어있지만, 편의상 빈 리스트라 생각하자)

[26][45][53][93] + [17][20][33][62]
 ^^                     ^^
[17][  ][  ][  ][  ][  ][  ][  ]

오른쪽의 17이 들어간다. 그럼 오른쪽의 인덱스는 1 증가하고 다시 비교한다.

[26][45][53][93] + [17][20][33][62]
 ^^                         ^^
[17][20][  ][  ][  ][  ][  ][  ]

이번에도 오른쪽에서 가져왔다. 다음 순서

[26][45][53][93] + [17][20][33][62]
     ^^                     ^^
[17][20][26][  ][  ][  ][  ][  ]

이번에는 왼쪽에서 가져왔다.

[26][45][53][93] + [17][20][33][62]
     ^^                         ^^
[17][20][26][33][  ][  ][  ][  ]

계속 가져와보자.

[26][45][53][93] + [17][20][33][62]
         ^^                     ^^
[17][20][26][33][45][  ][  ][  ]

다음,

[26][45][53][93] + [17][20][33][62]
             ^^                 ^^
[17][20][26][33][45][53][  ][  ]

그리고

[26][45][53][93] + [17][20][33][62]
             ^^                 
[17][20][26][33][45][53][62][  ]

이제 오른쪽에서는 전부 가져왔다. 왼쪽이 남았으니 그냥 가져와서 채운다.

[17][20][26][33][45][53][62][93]

각 왼쪽과 오른쪽도 동일한 방식으로 처리한다. 결국 재귀적으로 처리되는 셈인데 원소가 없거나 하나 밖에 없는 경우는 이미 정렬된 상태로 보면 이들이 이 재귀의 베이스 케이스가 될 것이다. 이를 코드로 구현해보자.

def mergeSort(alist):
    print("Spilting: ", alist)
    if len(alist) > 1:
        mid = len(alist) // 2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]
        mergeSort(lefthalf)
        mergeSort(righthalf)
        i, j, k = (0, 0, 0)
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                alist[k] = lefthalf[i]
                i += 1
            else:
                alist[k] = righthalf[j]
                j += 1
            k += 1
        while i < len(lefthalf):
            alist[k] = lefthalf[i]
            i += 1
            k += 1

        while j < len(righthalf):
            alist[k] = righthalf[j]
            j += 1
            k += 1
    print("Merging: ", alist)

alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
mergeSort(alist)
print(alist)

  1. 재귀호출에서 더 이상 내려갈 재귀 단계가 없는 조건으로 리턴을 시작하는 조건