합병 정렬(merge sort)를 파이썬으로 구현해보자!
합병 정렬이 무엇인지에 대한 자세한 설명은 어제 TIL (클릭) 을 참고
분할
합병 정렬의 핵심은 분할과 정복!
그 중 첫 단계인 분할을 하기 위한 코드를 구현했다.
배열의 전체 길이를 length에 저장한 후, 길이의 중앙값을 구해 mid에 저장했다.
배열의 길이가 홀수인 경우에는 왼쪽 배열에 하나 더 많이 들어가도록 설정했다.
mid를 이용해 배열을 반으로 나눈 후, 각각 left와 right 변수에 담아줬다.
그리고 두 변수를 인자로 하여 merge_sort()를 다시 호출하여 계속해서 배열을 쪼갰다.
배열에 원소의 개수가 1개만 남는 mid == 1 인 상황이 되면
함수를 return 했는데, 이때 바로 병합을 하는 merge() 함수를 호출한다.
인자로는 직전에 쪼갰던 left와right 배열이 들어간다.
def merge_sort(arr):
length = len(arr)
mid = length // 2 # 원소 개수의 홀짝 여부에 따라 중앙값 설정
left, right = arr[:mid], arr[mid:] # 두 리스트에 나눠서 담기
if mid == 1: # 원소 개수가 한개가 되면 병합 (중앙값이 1이면 양쪽 원소가 1개씩)
return merge(left, right)
left = merge_sort(left) # 계속 쪼개기
right = merge_sort(right)
return merge(left, right)정복 (합병/병합)
merge_sort()에서 호출된 merge()는 병합 과정을 수행한다.
우선 새롭게 합병된 merged_list 배열을 선언한 후,
인자로 들어온 left와 right 배열의 리스트가 모두 빈 리스트가 될 때까지, 반복문을 수행했다.
원래는 양쪽 배열의 값만 비교하여, 작은 값을 새로운 리스트에 추가하고(append) 기존 배열에서 제거(pop)만 했는데,
이렇게 했더니, 한쪽 배열에 요소가 없을 경우에 더 이상 비교가 불가능해서, IndexError: list index out of range 가 나왔다.
그래서 한쪽 리스트가 빈 경우, 남은 한쪽 리스트는 전부 병합된 리스트에 추가하도록 if 조건을 추가했다.
def merge(left, right):
merged_list = []
while left or right: # 두 리스트가 모두 비어있으면, while문 종료
if not left: # 리스트 한쪽이 빈 경우, 나머지 리스트를 전부 넣는 코드 (없으면 out of value)
merged_list += right
right = False
elif not right:
merged_list += left
left = False
else:
if left[0] >= right[0]: # right 값이 더 작으면
merged_list.append(right[0]) # right 값을 넣고 뺀다
right.pop(0)
else:
merged_list.append(left[0])
left.pop(0)
return merged_list예를 들어 [54, 34, 41, 89] 가 있을 때,
[54, 34], [41, 89][54] [34]
로 쪼개지고 나면 merge를 수행한다.
[34, 54]로 합치고 나면, 다시 right도 쪼개기를 수행하고 [41, 89]도 합친다.
그럼 마지막으로 return에서 다시 merge를 호출하여
두 배열도 합치면, 아래와 같이 정렬된 배열이 나온다.
[34, 41, 54, 89]
분할 정복 과정
분할과 정복 때마다 나오는 각 배열을 출력해보면
아래 이미지와 같이 분할, 정복(합병)을 통해 정렬이 이루어지는 것을 알 수 있다.
전체 코드 (Github)
def merge(left, right):
merged_list = []
while left or right: # 두 리스트가 모두 비어있으면, while문 종료
if not left: # 리스트 한쪽이 빈 경우, 나머지 리스트를 전부 넣는 코드 (없으면 out of value)
merged_list += right
right = False
elif not right:
merged_list += left
left = False
else:
if left[0] >= right[0]: # right 값이 더 작으면
merged_list.append(right[0]) # right 값을 넣고 뺀다
right.pop(0)
else:
merged_list.append(left[0])
left.pop(0)
return merged_list
def merge_sort(arr):
length = len(arr)
mid = (length // 2 + 1 if length %
2 else length // 2) # 원소 개수의 홀짝 여부에 따라 중앙값 설정
left, right = arr[:mid], arr[mid:] # 두 리스트에 나눠서 담기
if mid == 1: # 원소 개수가 한개가 되면 병합 (중앙값이 1이면 양쪽 원소가 1개씩)
return merge(left, right)
left = merge_sort(left) # 계속 쪼개기
right = merge_sort(right)
return merge(left, right)머리로는 어떤 알고리즘인지 알겠는데,
코드를 구현하는데 한참 걸리고..
다시 그 코드를 이해하는데 한참을 걸렸다..
오늘은 병합 정렬의 날로 기억될 것이다.. 🤞
