Processing math: 100%

새소식

반응형
컴퓨터공학 (Computer Science)/┗ 정렬 | Sorting

병합 정렬 (합병 정렬, Merge Sort)

  • -
반응형

병합 정렬은 프로그램 내장 방식으로 유명한 존 폰 노이만에 의해 제안된 정렬 알고리즘이다. 분할 정복법을 기반으로 하여 주어진 리스트를 분할하고 정렬하여 다시 병합한다.

병합 정렬은 최선, 최악, 평균 상황에서 항상 시간복잡도가 O(nlogn)임을 보장하며 stable한 알고리즘이다.

구현 방식에는 Top-down 방식과 Bottom-up 방식이 있다. 

다음 이미지는 병합 정렬의 과정을 보여준다. 출처는 위키피디아.

Animation of Merge Sort

 

다음 코드는 Top-down merge sort를 파이썬에서 구현한 것이다.

def topDownMergeRun(arr, a, b): clone = arr[a:b+1] topDownMerge(clone) arr[a:b+1] = clone def topDownMerge(arr): if len(arr) > 1: mid = len(arr) // 2 L = arr[:mid] R = arr[mid:] topDownMerge(L) topDownMerge(R) i = j = k = 0 while i < len(L) and j < len(R): if L[i] < R[j]: arr[k] = L[i] i+=1 else: arr[k] = R[j] j+=1 k+=1 while i < len(L): arr[k] = L[i] i+=1 k+=1 while j < len(R): arr[k] = R[j] j+=1 k+=1

다음 코드는 Bottom-up merge sort를 파이썬에서 구현한 것이다.

def bottomUpMergeRun(arr, a, b): clone = arr[a:b+1] bottomUpMerge(clone) arr[a:b+1] = clone def bottomUpMerge(arr): current_size = 1 while current_size < len(arr) - 1: left = 0 while left < len(arr)-1: mid = left + current_size - 1 right = ((2 * current_size + left - 1, len(arr) - 1)[2 * current_size + left - 1 > len(arr)-1]) merge(arr, left, mid, right) left = left + current_size*2 current_size = 2 * current_size def merge(a, l, m, r): n1 = m - l + 1 n2 = r - m L = [0] * n1 R = [0] * n2 for i in range(0, n1): L[i] = a[l + i] for i in range(0, n2): R[i] = a[m + i + 1] i, j, k = 0, 0, l while i < n1 and j < n2: if L[i] > R[j]: a[k] = R[j] j += 1 else: a[k] = L[i] i += 1 k += 1 while i < n1: a[k] = L[i] i += 1 k += 1 while j < n2: a[k] = R[j] j += 1 k += 1

 

병합 정렬의 아이디어는 외부 정렬 (External Sort)의 근간이 될 정도로 major한 알고리즘이다.

일정한 시간복잡도를 보장하지만 Auxiliary (보조배열)을 사용해야 한다는 단점이 있다. 이 때문에 callstack에 쌓이는 공간 외에도 O(n)의 공간을 추가로 사용한다.

물론 In-place하게 구현할 수는 있으나, 그 경우 시간복잡도가 O(n2)이 된다. 다음 코드는 in-place merge sort를 파이썬에서 구현한 것이다.

def inPlaceMerge(arr, start, mid, end): start2 = mid + 1 if (arr[mid] <= arr[start2]): return while (start <= mid and start2 <= end): if (arr[start] <= arr[start2]): start += 1 else: value = arr[start2] index = start2 while (index != start): arr[index] = arr[index - 1] index -= 1 arr[start] = value start += 1 mid += 1 start2 += 1 def inPlaceMergeSort(arr, l, r): if (l < r): m = l + (r - l) // 2 inPlaceMergeSort(arr, l, m) inPlaceMergeSort(arr, m + 1, r) inPlaceMerge(arr, l, m, r)
반응형

포스팅 주소를 복사했습니다

이 글이 도움이 되었다면 공감 부탁드립니다.