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