병합정렬
우리의 앞에 두 개의 정렬된 리스트 혹은 배열이 존재한다고 생각해봅시다.
이때, 두 리스트를 합쳐서 새롭게 정렬된 리스트를 만들고자 할 때 어떻게 해야 할까요?
오름차순으로 정렬된 상태이기 때문에 가장 앞에 있는 원소를 서로 비교해서 더 작은 원소를 새로운 리스트에 넣어주면 됩니다.
예를 들자면, 현 상황에서 1과 2를 비교해서 1이 더 작기 때문에 1을 새로운 리스트에 넣어줍니다.
그 다음은 3과 2를 비교해주면 되고 2가 3보다 작기 때문에 리스트에 넣어줍니다.
이 과정을 반복해서 최종적으로 1부터 10까지 오름차순으로 정렬된 리스트로 병합할 수 있게 됩니다.
이렇게 병합하면서 서로의 수를 비교하고 새롭게 리스트에 넣어주는 알고리즘이 병합 정렬입니다.
하지만, 우리가 원하는 것은 한 리스트를 정렬하는 것입니다. 그러면 내가 원하는 리스트를 정렬하기 위해서 병합 정렬을 어떻게 사용해야 할까요? 그 방법은 분리와 병합을 병행하여 사용하는 것입니다.
병합 정렬 사용
예를 들어 위와 같이 무작위로 섞인 정수형 배열이 있다고 가정해보겠습니다. 앞서 두 리스트를 비교해서 하나의 리스트로 만들어준 것처럼 두 개의 리스트로 만들겠습니다. 반으로 배열을 나누면 아래의 두 리스트를 얻을 수 있습니다.
하지만 여전히 정렬되지 않은 상태이기 때문에 다시 한 번 분할합니다.
일부 리스트는 오름차순이지만 일부는 그렇기 않기에 마지막으로 나누어줍니다.
각 리스트가 한 개의 원소만 가지기 때문에 우리는 두 개의 리스트를 비교해서 새 리스트에 넣어주는 작업을 진행하면 됩니다. 가장 앞에서부터 병합 정렬로 리스트를 만들겠습니다.
다시 역으로 병합해주면서 서로의 원소의 대소관계에 따라서 리스트에 넣어주는 작업을 진행합니다. 모든 작업이 진행되어 원소 2개로 이루어진 정렬된 리스트 4개가 생성되었습니다.
이제 슬슬 앞서 확인했던 병합 정렬과 비슷한 느낌이 들기 시작할 겁니다. 모든 리스트가 정렬된 상태이므로 우리는 각 리스트의 가장 앞에 있는 원소들을 비교하면서 더 작은 원소를 리스트에 넣어주는 작업을 이어가면 됩니다.
최종적으로 오름차순으로 정렬된 두 개의 리스트가 만들어졌으므로 가장 처음에 봤던 병합의 과정과 동일한 상황이 만들어졌습니다. 이제 우리가 할 것은 마지막으로 병합하면서 완성된 하나의 정렬된 리스트를 반환하는 것입니다.
위와 같이 일련의 과정을 분리와 병합의 과정을 거쳐서 최종적으로 정렬된 리스트를 가질 수 있습니다
복잡도
공간 복잡도
우리는 리스트를 정렬하기 위해서 하나의 새로운 리스트를 만들었습니다. 이때의 리스트는 원본 리스트와 같은 길이이기 때문에 배열의 길이 n과 똑같은 리스트 공간이 필요합니다.
따라서 병합 정렬의 공간 복잡도는 O(n)이 됩니다.
시간 복잡도
시간 복잡도는 O(nlogn)입니다.
1. 먼저 전체 리스트를 반으로 나누어 가면서 리스트를 분할합니다. 앞에서는 8의 길이를 가진 리스트를 3번 나누었습니다. 이때, 길이가 16이면 4번 리스트를 나누어서 분리와 병합을 진행할 것입니다. 즉, 2의 제곱수별로 리스트를 나누는 횟수가 늘어납니다. 정렬하고자 하는 리스트의 길이가 n이라고 하면 밑이 2인 수를 제곱하여 n이라는 수를 만들 수 있습니다. 결론적으로, log2n라는 수로 귀결되게 됩니다. 역으로 생각해보면 리스트의 길이가 n이라면 log2n의 연산을 수행해야 한다는 의미가 되는 것입니다.
2. 원소의 개수마다 분리와 병합이 나타나므로 n번의 연산이 필요합니다.
1과 2에 따라서 최종적으로 시간 복잡도는 O(nlogn)이 됩니다.
코드로 구현
1. 분리
가장 먼저 분리의 과정이 필요합니다. 분리할 때는 중간을 기준으로 2개의 리스트로 분리해줍니다.
def merge_sort(arr, left, right):
if (left < right):
mid = (left + right) // 2
merge_sort(arr, left, mid)
merge_sort(arr, mid + 1, right)이렇게 모든 원소에 대해 분리를 완료할 수 있습니다. 맨 위에서는 분리가 동시다발적으로 이루어졌으나, 재귀를 사용해서 분리하기 때문에 스택 구조로 가장 분리된 두 개의 리스트에서 왼쪽 리스트를 택하면서 분리를 이어나갑니다. 트리의 전위순회를 생각하면 됩니다.
2. 병합
분리된 리스트를 병합할 차례입니다. 아래의 두 리스트를 병합한다고 가정해보겠습니다.
먼저 두 리스트를 비교해 작은 값들을 받아줄 받아줄 리스트가 하나 필요합니다.
tmp = []
그리고 둘을 비교해줍니다. 이번 구현에서는 리스트를 쪼개지 않고 인덱스를 통해서 정렬하도록 하겠습니다. 그림으로 보자면 아래와 같습니다.
6과 4가 위치한 인덱스를 통해서 둘의 대소를 판별해 리스트에 넣어줍니다.
if arr[lp] <= arr[rp]:
tmp.append(arr[lp])
lp += 1
else:
tmp.append(arr[rp])
rp += 1
그런데 이렇게 비교하다가 어느 순간 한 쪽의 리스트를 모두 비교하여, 다른 쪽 리스트에만 원소가 존재하는 경우가 발생할 수 있습니다. 예를 들자면 아래와 같은 상황입니다.
이렇게 되면 그냥 단순히 리스트에 값을 넣어주기만 하면 됩니다.
while lp <= mid:
tmp.append(arr[lp])
lp += 1
while rp <= right:
tmp.append(arr[rp])
rp += 1왼쪽 리스트(위 그림에서는 위쪽 리스트)만 원소를 가질 수도 있고, 오른쪽 리스트(위 그림에서는 아래쪽 리스트)만 리스트를 가질 수 있어서 모든 상황을 커버해주기 위해 두 경우 모두 리스트에 저장해주도록 하겠습니다.
두 반복문은 동시에 발생할 수 없습니다. 왜냐하면 한쪽 리스트가 비었을 때 두 리스트를 비교하는 반복문을 벗어나기 때문입니다. 그래서 무조건 정렬된 상태로 저장되게 됩니다.
마지막으로, 우리는 인덱스를 통해서 새 리스트에 값들을 집어넣었습니다. 이때, 새 리스트를 원본 리스트에 업데이트 하기 위해서 반복문을 사용합니다.
for k in range(first, last + 1):
arr[k] = tmp[k - first]
# 혹은 슬라이싱 사용
arr[first:last + 1] = tmp
이 과정을 모두 합치면 아래와 같습니다.
def merge_sort(arr, first, last):
if (first < last):
mid = (first + last) // 2
merge_sort(arr, first, mid)
merge_sort(arr, mid + 1, last)
return merge(arr, first, last)
def merge(arr, first, last):
mid = (first + last) // 2
lp, rp = first, mid + 1
tmp = []
while lp <= mid and rp <= last:
if arr[lp] <= arr[rp]:
tmp.append(arr[lp])
inserted_value.append(arr[lp])
lp += 1
else:
tmp.append(arr[rp])
inserted_value.append(arr[rp])
rp += 1
while lp <= mid:
tmp.append(arr[lp])
inserted_value.append(arr[lp])
lp += 1
while rp <= last:
tmp.append(arr[rp])
inserted_value.append(arr[rp])
rp += 1
# for k in range(first, last + 1):
# arr[k] = tmp[k - first]
arr[first:last + 1] = tmp
return arr
마치며
사실 알고리즘을 코드로 구현하는 과정은 정해져있지 않습니다. 단지 알고리즘이 어떤 구조이며 어떠한 과정을 가지는지를 이해한 채로 코드를 구현하면 됩니다.
