병합 정렬
Merge Sort
입력을 2개의 부분 문제로 분할하고, 부분 문제의 크기가 1/2로 감소하는 분할 정복 알고리즘이다.
즉, n개의 숫자들을 n/2개씩 2개의 부분 문제로 분할하고, 각각의 부분 문제를 순환적으로 병합 정렬한 후, 2개의 정렬된 부분을 1개로 병합하여 정렬(정복)한다.
요악하면, 정렬되지 않은 배열을 받았을 때 원소의 개수가 1이 될 때까지 반으로 계속 나누다가, 원소의 개수가 1이 되면 그때부터 나눠왔던 원소들의 값을 비교해서 합치는 것이다.
병합 정렬의 시간복잡도는 O(NlogN)이다.
병합할 때 k개의 층이 생기고 이때 k = log2(N)이다.
n > n/2 (1층) > n/4 = n/(2^2) (2층) > n/8 = n/(2^3) (3층)
k번 1/2로 나누면, k개의 층이 생기고 2^k = n, k = log2(n)
각 층마다 수행된 비교 횟수는 O(n)이다.
따라서 병합 정렬의 시간복잡도는 층 개수 각 층마다 수행된 비교 횟수 = log(N) O(N) = O(NlogN)이다.
소스코드
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
def merge_sort(array):
if len(array) <= 1:
return array
mid = len(array) // 2
left_array = merge_sort(array[:mid])
right_array = merge_sort(array[mid:])
# print("merge_sort" + str(left_array), str(right_array))
return merge(left_array, right_array)
def merge(left, right):
merged_array = []
l, r = 0, 0
while l < len(left) and r < len(right):
if left[l] < right[r]:
merged_array.append(left[l])
l += 1
else:
merged_array.append(right[r])
r += 1
# print(merged_array, left[l:], right[r:])
merged_array += left[l:]
merged_array += right[r:]
# print(merged_array)
return merged_array
sorted_array = merge_sort(array)
print(sorted_array)
함수 설명
-
merge_sort 함수는 재귀호출 되는 함수로, 배열의 길이가 1보다 작거나 같으면(원소의 개수가 1이면) return 한다.
mid 값을 기준으로 배열을 왼쪽 배열과 오른쪽 배열로 나누고 merge_sort 함수를 재귀호출 한다.
merge 함수를 호출해 왼쪽 배열과 오른쪽 배열을 정렬하여 병합한다. -
merge 함수는 while문을 돌면서 left와 right 배열의 원소를 비교하며 둘 중 작은 값을 merged_list에 넣는다.
while문을 다 돌은 후 남은 원소에 대해 통째로 merged 배열에 넣는다.
과정 설명
주석된 부분을 해제하면 출력문은 다음과 같다.
merge_sort[7] [5]
[5] [7] []
[5, 7]
merge_sort[0] [3]
[0] [] [3]
[0, 3]
merge_sort[9] [0, 3]
[0, 3] [9] []
[0, 3, 9]
merge_sort[5, 7] [0, 3, 9]
[0, 3, 5, 7] [] [9]
[0, 3, 5, 7, 9] # 처음 왼쪽 배열 정렬 끝
merge_sort[1] [6]
[1] [] [6]
[1, 6]
merge_sort[4] [8]
[4] [] [8]
[4, 8]
merge_sort[2] [4, 8]
[2] [] [4, 8]
[2, 4, 8]
merge_sort[1, 6] [2, 4, 8]
[1, 2, 4, 6] [] [8]
[1, 2, 4, 6, 8] # 처음 오른쪽 배열 정렬 끝
merge_sort[0, 3, 5, 7, 9] [1, 2, 4, 6, 8]
[0, 1, 2, 3, 4, 5, 6, 7, 8] [9] []
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]