병합 정렬
존 폰 노이만이 고안.
•
나누고 합치는 알고리즘
알고리즘
1.
정렬할 데이터 집합을 반으로 나눈다.
2.
나누어진 하위 데이터 집합의 크기가 2 이상이면 이 하위 데이터 집합에 대해 1을 반복한다.
3.
원래 같은 집합에서 나뉘어져 나온 하위 데이터 집합 둘을 병합하여 하나의 데이터 집합으로 만든다. 단 병합할 때 데이터 집합의 원소는 순서에 맞춰 정렬한다.
4.
데이터 집합이 다시 하나가 될 때까지 3을 반복한다.
핵심은 “병합 할 때 데이터 집합의 원소는 순서에 맞추어 정렬” 하는 데에 있다.
1.
두 데이터 집합을 합한 것 만큼 비어있는 데이터 집합을 마련한다.
2.
두 데이터 집합의 첫 번째 요소들 끼리 비교하여 더 작은 요소를 새 데이터 집합에 추가, 추가된 데이터는 원래 데이터 집합에서 삭제
3.
양쪽 데이터 집합이 빌 때까지 2 과정을 반복한다.
def merge_sort(array: List):
if len(array) <= 1:
return array
mid = len(array) // 2
left = merge_sort(array[:mid])
right = merge_sort(array[mid:])
return merge(left, right)
def merge(left, right):
result = []
while len(left) > 0 or len(right) > 0:
if len(left) > 0 and len(right) > 0:
if left[0] <= right[0]:
result.append(left[0])
left = left[1:]
else:
result.append(right[0])
right = right[1:]
elif len(left) > 0:
result.append(left[0])
left = left[1:]
elif len(right) > 0:
result.append(right[0])
right = right[1:]
return result
Python
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
print("arr : ", arr)
return merge(left, right)
def merge(left, right):
result = []
while left or right:
if left and right:
if left[0] <= right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
elif left:
result.append(left.pop(0))
elif right:
result.append(right.pop(0))
return result
Python
