이 포스트는 파이썬에서 병합 정렬 알고리즘을 구현한 포스트입니다.
필자의 티스토리 블로그에서도 병합 정렬을 구현한 포스트를 포스팅했지만 여기서는 그 코드를 조금 개량하였습니다.
병합 정렬(Merge sort)이라는 것은 합병 정렬이라고도 하는데, 말 그대로 병합해서 정렬하는 방법입니다. 어떻게 정렬하느냐 하면, 우선 정렬을 수행할 배열의 크기(원소의 개수)가 0 혹은 1이면 정렬이 완료된 것으로 보고 2 이상일 경우 정렬을 하는데 예를 들어 원소가 8개일 경우 이를 반씩 나눠서 원소가 4개인 배열 둘로 나누고 그것을 또 반씩 나눠서 원소가 2개인 배열로 나누고 하면서 모든 배열이 하나의 원소만을 가질 때까지 계속 나누어 나갑니다. 그 후에는 다시 합쳐야 하는데 이 때는 나눈 순서의 역순으로 둘씩 합쳐 나가되 이 과정에서 본격적으로 정렬을 하는 것입니다.
알기 쉽게 그림으로 나타내면 다음과 같습니다.
보는 바와 같이 나눌 때는 위치에 맞게 반씩 나누지만 다시 합칠 때는 양쪽에서 값을 비교하면서 정렬을 수행하는 것입니다. 합쳐진 배열은 정렬이 된 상태이므로 마지막으로 합칠 때는 정렬이 완료됩니다.
이를 파이썬으로 구현한 코드는 다음과 같습니다.
def merge_sort(arr, desc = False): if len(arr) <= 1: return arr # only 2 or more half = len(arr) // 2 # divide by 2 L = merge_sort(arr[:half], desc) # Left: first half R = merge_sort(arr[half:], desc) # Right: except first half mer = [] # array for result while len(L) > 0 and len(R) > 0: if (L[0] > R[0] and not desc) or (L[0] < R[0] and desc): mer.append(R[0]); R.pop(0) # append R[0] and remove else: mer.append(L[0]); L.pop(0) # append L[0] and remove # if out of L or R, append rest if len(L) > 0: mer += L if len(R) > 0: mer += R return mer # return
먼저 위와 같이 함수를 정의합니다. 인자는 정렬을 수행할 배열과 내림차순 여부(True/False)입니다. 내림차순 여부를 생략하면 오름차순으로 정렬됩니다.
2번 줄에서 우선 배열 크기를 검사해서 1 이하일 경우 그냥 그 값을 그대로 돌려주는 코드를 넣습니다. 파이썬으로 퀵 정렬 알고리즘 구현하기에서 구현했던 바와 같이 배열을 쪼개면서 재귀하는 방식을 사용하기 때문입니다. 그리고 배열 크기가 2 이상일 경우 3번 줄에서 배열 크기를 반으로 나눈 값을 구한 다음(소수점 이하는 버림) 그 값을 기준으로 배열을 나눠서 4번 줄과 5번 줄에서 함수를 재귀호출합니다. 또 6번 줄에서는 쪼개진 배열을 정렬 상태로 다시 합치기 위해 빈 배열 변수를 선언합니다.
8번 줄은 반복문입니다. 반복 조건은 양쪽 배열 모두에 하나 이상의 원소가 남아 있을 때입니다.
9번 줄에서 정렬을 위한 비교를 수행합니다. 비교하는 방법은 양쪽 배열의 0번 원소 크기로 합니다.
- 오름차순일 경우는 오른쪽이 왼쪽보다 더 클 때, 내림차순일 경우는 왼쪽이 오른쪽보다 더 클 때 10번 줄과 같이 큐 방식을 써서 오른쪽 배열의 0번 원소를 합칠 배열에 추가하고 오른쪽 배열의 0번 원소는 삭제합니다.
- 그 외의 경우는 반대로 왼쪽 배열의 0번 원소를 합칠 배열에 추가하고 왼쪽 배열의 0번 원소를 삭제합니다.
주: 자료구조론에서 큐(Queue)는 들어온 순서대로 데이터가 나오는 방식을 뜻하는 말입니다. 이와 반대로 들어온 순서의 역순으로 데이터가 나오는 방식은 스택(Stack)이라고 합니다. 예를 들어, 데이터가 들어온 순서가 1, 2, 3, 4, 5라면 큐의 경우 1, 2, 3, 4, 5 순서대로 데이터가 나오고 스택의 경우 5, 4, 3, 2, 1 순서대로 데이터가 나옵니다.
반복문을 통해 왼쪽 배열과 오른쪽 배열 중 한 쪽이 모두 없어지면 남아있는 다른 한 쪽을 전부 합칠 배열에 추가합니다. 먼저 왼쪽이 남아있다면 14번 줄에서 왼쪽 배열의 남은 값들을 합칠 배열에 추가하고 오른쪽이 남아있다면 15번 줄에서 오른쪽 배열의 남은 값들을 추가합니다.
그리고 최종적으로 16번 줄에서 합친 배열의 결과를 함수의 값으로 돌려줍니다.
이제 이 함수를 실험해 봅시다.
unsorted = [6, 4, 1, 7, 8, 5, 2, 3]
print(" Unsorted: %s" % unsorted)
print(" Ascending: %s" % merge_sort(unsorted) )
print("Descending: %s" % merge_sort(unsorted, True) )
정렬되지 않은 배열을 세팅한 다음 정렬 함수를 오름차순과 내림차순으로 실행해 보면,
Unsorted: [6, 4, 1, 7, 8, 5, 2, 3] Ascending: [1, 2, 3, 4, 5, 6, 7, 8] Descending: [8, 7, 6, 5, 4, 3, 2, 1]
정렬된 배열이 출력됩니다.
이와 같이 파이썬에서 병합 정렬 알고리즘을 구현해 볼 수 있습니다.