병합 정렬(Merge Sort)이란
- 가장 작은 단위가 될 때까지 반으로 가른 후 단계별로 합쳐질 때 정렬을 수행하는 정렬 알고리즘
- 원소가 하나인 N개의 배열로 나누어져 정렬을 시작할 때(0단계)
- 1단계 : 배열을 두개씩 합치기. 각 배열은 원소 두개씩 가지게 된다.
- 2단계 : 배열을 두개씩 합치기. 각 배열은 원소 네개씩 가지게 된다.
- 3단계 : 배열을 두개씩 합치기. 각 배열은 원소 여덟개씩 가지게 된다.
- … 단계의 크기는 logN, 정렬 수행 시간은 N을 유지
- 따라서, 시간복잡도는 O(NlogN)
코드로 표현하기
- 원소 하나를 가지는 배열이 될 때까지 중간값 기준 두 그룹으로 가르는
mergeSort함수 정의가 필요하다.(재귀 사용) - 갈라진 배열들을 다시 합치며 정렬하는
merge함수 정의가 필요하다. - left그룹과 right그룹은 항상 첫번째 요소부터 조회하며(i=0, j=0), 이때 크기 비교를 수행하여 새로운 리스트(v)에 저장해준다.
- 한쪽 그룹이 마지막 인덱스값을 가리켜 더이상 크기비교를 할 수 없다면, 다른 한쪽 그룹의 나머지 요소들을 순서대로 리스트(v)에 추가시킨다.
#오름차순 정렬 예제
arr = [7, 6, 5, 8, 3, 5, 9, 1] #임의의 배열
def merge(left, right):
i = 0
j = 0
v = [] #정렬된 값을 저장할 공간
while i < len(left) and j < len(right):
#두 그룹의 현재 요소 크기 비교에 따라 v에 값 저장
if left[i] <= right[j]:
v.append(left[i])
i += 1
else:
v.append(right[j])
j += 1
#left그룹을 모두 조회했다면 right의 남은 요소들을 추가
if i == len(left):
v = v + right[j:]
#right그룹을 모두 조회했다면 left의 남은 요소들을 추가
if j == len(right):
v = v + left[i:]
#정렬 완료한 리스트를 리턴
return v
def mergeSort(a):
#원소가 하나라면 정렬이 필요없으므로 그대로 반환
if len(a) <=1:
return a
middle = len(a) // 2 #중간값
left = mergeSort(a[:middle]) #중간값 기준 왼쪽 그룹
right = mergeSort(a[middle:]) #중간값 기준 오른쪽 그룹
return merge(left, right)
result = mergeSort(arr)
#출력 결과
for i in result:
print(i, end=" ")
참조문서
https://blog.naver.com/ndb796/221227934987 https://leedakyeong.tistory.com/entry/알고리즘-파이썬으로-병합-정렬-구현하기-merge-sort-in-python-bottom-up-방식