합병 정렬(Merge Sort)이란?
입력이 2개의 부분 문제로 분할되고, 부분 문제의 크기가 1/2로 감소하는 분할 정복 알고리즘입니다.
즉, n개의 숫자들을 n/2개씩 2개의 부분문제로 분할하고, 각각의 부분 문제를 순환적으로 합병 정렬한 후, 2개의 정렬된 부분을 합병하여 정렬(정복)합니다. 즉, 합병 과정이 정복하는 것입니다.
→ 합병이란?
2개의 각각 정렬된 숫자들을 1개의 정렬된 숫자들로 합치는 것입니다.
합병 정렬이 어떻게 정렬하는지 감이 안 잡히실 수도 있는데, 이 그림 한 장이면 어떤 알고리즘이신지 알 수 있습니다.
(화살표 옆 숫자는 실행 순서를 의미합니다.)
합병 정렬 수행 과정을 설명해 보도록 하겠습니다.
맨 위에 원소의 개수가 8인 배열이 정렬되지 않은 채 있습니다.
저 배열을 정렬하기 위한 방법은 반으로 나누어 다시 합병정렬을 하는 것입니다.
<원소의 개수 4>
자, 반으로 나누었습니다. 하지만 이 배열을 정렬하기 위한 방법 또한 반으로 나누어 다시 합병 정렬을 수행하는 것입니다.
| 37 | 10 | 22 | 30 |
<원소의 개수 2>
다시 반으로 나누었습니다. 이 배열을 정렬하기 위한 방법은 또, 반으로 나누어 다시 합병정렬을 수행하는 것입니다.
(원소의 개수가 1이 될 때까지 반복)
| 37 | 10 |
<원소의 개수 1>
이제 원소의 개수가 1이 되었습니다. <원소의 개수 2> 일 때의 배열의 왼쪽과 오른쪽이 정렬된 셈인 것입니다. (단 1개이므로 정렬된 것이나 다름없다)
더 이상 반으로 나눌 수 없으니 이제 합병(정복)하는 과정에 들어가야 합니다.
두 원소의 크기를 비교해 작은 것부터 임시 배열에 넣습니다. (오름차순)
| 37 |
| 10 |
| 10 | 37 |
<원소의 개수 4> 일 때 왼쪽 배열을 정렬했으니, 이제 오른쪽 배열을 위와 같은 과정을 거쳐 정렬합니다. 그렇다면 아래와 같은 배열이 나옵니다.
| 22 | 30 |
왼쪽과 오른쪽을 정렬했다면, 이제 왼쪽 배열과 오른쪽 배열의 원소를 하나하나 비교해 작은 것부터 다시 넣습니다.
| 10 | 22 | 30 | 37 |
이렇게 되면 <원소의 개수 8> 일 때의 왼쪽 배열을 정렬한 것입니다. 이제 <원소의 개수 8> 일 때의 오른쪽 배열(35, 13, 25, 24))도 위와 같은 과정을 거쳐 아래와 같이 정렬된다면, 이 왼쪽 배열(10, 22, 30, 37)과 비교해서 배열을 완성합니다.
| 13 | 24 | 25 | 35 |
그렇게 되면 정렬을 다 한 것입니다.
한 마디로 요약하자면, 정렬되지 않은 배열을 받으면 그냥 원소의 개수가 1이 될 때까지 반으로 계속 나누다가, 원소의 개수가 1이 된다면 그때부터 나눠왔던 원소들의 값을 비교해서 합치는 것입니다.
어느 정도 감을 잡으셨을 거라 믿습니다 :)
▶ 합병 정렬 알고리즘 수도 코드
MergeSort(A,p,q)
입력: A[p] ~ A[q]
출력: 정렬된 A[p] ~ A[q]
if ( p < q ) { //line 1
k = |(p + q) / 2| //line 2
MergeSort(A,p,k) //line 3
MergeSort(A, k+1, q) //line 4
A[p]~A[k]와 A[k+1]~A[q]를 합병한다. //line 5
}
→ line 1: 정렬할 부분의 원소의 수가 2개 이상일 때에만 다음 단계가 수행되도록 합니다. 만일 p = q(즉, 원소의 수가 1)이면, 그 자체로 정렬된 것이므로 line 2~5가 수행되지 않은 채 이전 호출했던 곳으로 리턴합니다.
→ line 2: 정렬할 부분의 원소들을 1/2로 나누기 위해, k = |(p + q) / 2|를 계산합니다. (단, 원소의 수가 홀수인 경우, k는 소수점 이하를 버린 정수)
→ line 3~4: MergeSort(A, p, k)와 MergeSort(A, k+1, q)를 순환 호출하여 각각 정렬합니다.
→ line 5: line 3~4에서 각각 정렬된 부분을 합병합니다. 합병 과정의 마지막에는 임시 배열에 있는 합병된 원소들을 배열 A로 복사합니다. 즉, 임시 배열 B[p] ~ B[q]를 A[p] ~ A[q]로 복사합니다.
▶ 합병 정렬 알고리즘 코드
이제 파이썬으로 그 코드를 짜 봅시다.
저는 다른 unsorted라는 파일에 정렬되지 않은 숫자들을 numbers라는 리스트에 저장해놨습니다.
이 코드를 실행해보시려면 sublist에 직접 숫자들을 넣으시면 됩니다.
from unsorted import numbers
sublist = numbers[:50]
def mergeSort(list):
size = len(list)
if size <= 1: return list
mid = len(list) // 2
left = mergeSort(list[:mid])
right = mergeSort(list[mid:])
merged = merge(left, right)
return merged
def merge(list1, list2):
merged = []
while len(list1) > 0 and len(list2) > 0:
if list1[0] <= list2[0]:
merged.append(list1.pop(0))
else:
merged.append(list2.pop(0))
if len(list1) > 0:
merged += list1
if len(list2) > 0:
merged += list2
return merged
sorted = mergeSort(sublist)
print (sorted)
먼저 mergeSort(list) 함수를 살펴봅시다.
mergeSort는 mid = len(list) // 2 , 배열을 1/2로 나누기 위해 배열의 중간 인덱스를 구합니다.
그렇게 나누어진 왼쪽 배열과 오른쪽 배열에 각각 다시 mergeSort 함수를 호출합니다.
mergeSort함수를 통해 정렬된 왼쪽 배열과 오른쪽 배열을 합병하기 위해 merge함수를 호출합니다.
그리고 재귀호출을 끝내기 위한 조건으로 배열의 길이가 1보다 작거나 같으면(= 원소의 개수가 1이면) return 합니다.
def mergeSort(list):
size = len(list)
if size <= 1: return list
mid = len(list) // 2
left = mergeSort(list[:mid])
right = mergeSort(list[mid:])
merged = merge(left, right)
return merged
그 다음 merge(list1, list2) 함수를 봅시다.
먼저 왼쪽 배열과 오른쪽 배열을 합칠 임시 배열 merged를 선언합니다.
그리고 while문을 돌면서 list1 또는 list2의 원소를 모두 검사하기 전까지 list1과 list2의 원소를 비교해 둘 중 작은 값을 merged에 넣습니다.
아래와 같이 while문을 다 돌고 난 후에 아직 검사하지 않은 원소가 있는 배열이 있다면 그 배열은 통째로 merged 배열에 넣습니다.
def merge(list1, list2):
merged = []
while len(list1) > 0 and len(list2) > 0:
if list1[0] <= list2[0]:
merged.append(list1.pop(0))
else:
merged.append(list2.pop(0))
if len(list1) > 0:
merged += list1
if len(list2) > 0:
merged += list2
return merged
하지만 코드를 이렇게 짠다면, 메모리를 불필요하게 사용합니다.
mergeSort함수를 보면 원래의 리스트를 반으로 나누기 때문입니다.
예를 들어, 100만개의 원소를 가진 전체 리스트가 있다고 가정한다면, mergeSort를 다시 호출할 때에 각각 50만개 원소를 가진 리스트를 생성합니다. 또 다음 단계로 가면 25만개와 25만개의 리스트를 생성하게 됩니다.
mergeSort함수는 재귀호출함수이기 때문에 현시점까지 생성한 리스트는 소멸되지 않고, 아직 그대로 존재합니다. (함수가 종료되지 않았기 때문에)
이렇게 mergeSort를 호출할 때마다 배열을 분리하는 과정(부분 배열을 생성하는 과정)이 생깁니다.
조금 다른 방법으로 해봅시다.
▶ 합병 정렬 알고리즘 코드 - 임시배열 사용 X ver
from unsorted import numbers
sublist = numbers[:50]
def mergeSort(list,p,q): #q= inclusive
if p>= q: return
mid = (p + q) // 2
mergeSort(list, p, mid)
mergeSort(list, mid+ 1, q)
merge(list, p, mid + 1, q)
def merge(list, left, right, end):
merged = []
l, r = left, right
while l < right and r <= end:
if list[l] <= list[r]:
merged.append(list[l])
l +=1
else:
merged.append(list[r])
r +=1
while l < right:
merged.append(list[l])
l +=1
while r <= end:
merged.append(list[r])
r+=1
l = left
for n in merged:
list[l] = n
l +=1
print(sublist)
sorted = mergeSort(sublist, 0, len(sublist) - 1)
print(sublist)
앞서 봤던 코드와 차이점이 있습니다. 바로 각 함수마다 return값이 없습니다. 바로 임시배열을 사용하지 않는다는 것입니다. mergeSort에는 이제 함수 인자로 정렬하고자 하는 전체 배열과 배열의 왼쪽 인덱스와 오른쪽 인덱스를 전달합니다. 전에는 계속 생성하던 부분 배열을 전달했다면, 이제는 정렬하고자 하는 전체 배열을 전달합니다.
def mergeSort(list,p,q): #q= inclusive
if p>= q: return
mid = (p + q) // 2
mergeSort(list, p, mid)
mergeSort(list, mid+ 1, q)
merge(list, p, mid + 1, q)
merge함수 입니다.
함수 인자로는 전체 list와 왼쪽 배열의 시작 인덱스 left, 오른쪽 배열의 시작 인덱스 right, 오른쪽 배열의 마지막 인덱스 end를 받습니다.
위에서 봤던 코드와 같이 합치기 위한 merged라는 배열을 준비합니다.
왼쪽 배열과 오른쪽 배열의 시작을 가리키는 각각의 변수 l 과 r을 하나씩 증가해나가면서 값을 비교한 후
작은 값을 merged에 넣습니다.
while문을 다 돌고 나면 아직 원소가 남아있는 배열을 통째로 merged에 넣습니다.
for n in merged:
그리고 처음 봤던 코드와 다르게 정렬된 merged를 원래의 배열인 list에 넣습니다.
예를 들면 위 그림과 같습니다. 현재 배열 list[4~5]와 list[6~7]이 합병하고자 하는 배열이고, 이를 비교하고 오름차순으로 merged 배열에 넣습니다. 그리고 그 merged, 정렬된 배열의 값으로 list[4~7] 값을 바꿉니다.
def merge(list, left, right, end):
merged = []
l, r = left, right
while l < right and r <= end:
if list[l] <= list[r]:
merged.append(list[l])
l +=1
else:
merged.append(list[r])
r +=1
while l < right:
merged.append(list[l])
l +=1
while r <= end:
merged.append(list[r])
r+=1
l = left
for n in merged:
list[l] = n
l +=1
첫 번째와 두 번째 코드를 살펴 보았습니다. 아마 실행해보시면 첫 번째 코드보다 두 번째 코드가 실행시간이 더 짧은 것을 보실 수 있습니다.
알고리즘은 빅오 표기로 나타내면 시간복잡도가 2n이든 3n이든 똑같아지지만, 상수 값을 줄이는 것도 효율적인 알고리즘을 위한 방법 중 하나입니다. 이 코드는 바로 그 상수 값을 줄이는 것과 같습니다.
▶ 합병 정렬의 시간 복잡도
정렬의 시간복잡도는 일반적으로 숫자의 비교 횟수로 나타냅니다.
앞서 봤던 이 그림을 봤을 때, 분할하는 부분은 배열의 중간 인덱스 계산과 2번의 순환 호출을 하는 것이므로 O(1) 시간이 걸립니다.
반면에 합병을 하는 수행 시간은 입력 크기에 비례합니다. 즉, 2개의 정렬된 배열 A와 B의 크기가 각각 n과 m이라면, 최대 비교 횟수는 (n+m - 1)입니다. 왜냐하면 합병하는데 2개의 숫자를 1번 비교할 때마다 하나의 '승자'가 합병된 배열 C에 저장되기 때문입니다. 따라서 배열 C에는 n+m개의 원소가 있겠지만, 가장 마지막에 저장되는 숫자는 비교할 대상이 없기 때문에 최대 비교 횟수는 (n+m - 1)입니다. 즉, 합병하는 부분의 시간복잡도는 O(m+n)입니다.
위 그림에서 각 층을 살펴보면 모든 숫자가 합병에 참여하고 있습니다. 합병의 수행시간은 합병되는 입력 크기에 비례하므로 각 층에서 수행된 비교 횟수는 O(n)입니다.
마지막에 임시 배열의 합병된 원소들을 원래 입력이 저장된 배열로 복사하는 시간을 살펴보면, 층마다 모든 n개의 원소가 복사되므로 이때 걸리는 시간도 O(n)입니다. 따라서 각 층에서의 비교 횟수와 같은 복잡도이므로, 이 둘을 합하여도 각 층에서의 시간복잡도는 O(n) 입니다.
(층은 위 그림에서 맨 밑에서부터)
| 입력크기 | 층 |
| n | |
| n/2 | 1층 |
| n/4 = n/2^2 | 2층 |
| n/8 = n/2^3 | 3층 |
입력 크기 n을 계속하여 1/2로 나누다가, 더 이상 나눌 수 없는 크기인 1이 될 때 분할을 중단합니다.
따라서 k번 1/2로 나누었다면 k개의 층이 생기는 것이고, 2^k = n 이므로 k = log2(n)임을 알 수 있습니다.
즉, 합병할 때 k개의 층이 생긴다는 것입니다. 그렇다면 각 층마다 O(n)의 시간복잡도를 가졌으니, 합병 정렬 알고리즘의 시간 복잡도는 층 개수(k) * O(n) = O(nlogn) 이 됩니다. (시간복잡도에서 logn을 말할 때 보통 밑이 2입니다.)
▶ 합병 정렬의 공간 복잡도
공간복잡도는 합병된 결과를 저장할 입력 크기와 같은 임시 배열이 하나 더 필요하기 때문에 공간 복잡도는 O(n) 입니다.
대부분의 정렬 알고리즘들은 입력을 위한 메모리 공간과 O(1) 크기의 메모리 공간만을 사용하면서 정렬 수행하기 때문에 이는 합병 정렬의 단점입니다.
+O(1) 크기의 메모리 공간이란, 입력 크기 n과 상관 없는 크기의 공간. ex) 변수, 인덱스 등
▶ 합병 정렬의 적용
합병 정렬은 외부 정렬의 기본이 되는 정렬 알고리즘입니다.
연결 리스트에 있는 데이터를 정렬할 때에도 퀵 정렬이나 힙 정렬보다 훨씬 효율적입니다.
멀티코어 CPU와 다수의 프로세서로 구성된 그래픽 처리 장치의 등장으로 정렬 알고리즘을 병렬화하는 데에 합병 정렬 알고리즘이 활용됩니다.
오류나 오타 지적 언제든 환영입니다. :)
참고: 알기 쉬운 알고리즘(양성봉)
'Algorithm > Divide-and-Conquer' 카테고리의 다른 글
| [알고리즘 공부] 최근접 점의 쌍 찾기 알고리즘(Closest Pair of Points) - python 파이썬 (0) | 2021.10.21 |
|---|---|
| [ 알고리즘 공부 ] 선택 문제 알고리즘(Selection) (feat.python 파이썬) (0) | 2021.10.07 |
| [ 알고리즘 공부 ] 퀵정렬 퀵소트(Quick Sort) - 분할 정복 알고리즘(feat. python 파이썬) (0) | 2021.10.06 |
