[알고리즘] Merge sort :: 병합정렬

O(n*logn)의 성능을 나타내는 병합정렬(합병정렬)을 파이썬으로 구현할 것이다.

 

병합정렬

힙정렬, 퀵정렬만큼 빠른 정렬 알고리즘이다.

병합정렬은 크게 분할과 병합과정으로 나누어진다.

과정 요약

배열의 모든 원소들을 하나씩 분할한 후, 각 원소들끼리 비교하며 다시 병합하는 과정을 거친다.

과정

1. 배열을 하나씩 분해할때 까지 분해한다.

2. 분해한 후 서로 비교하며 오름차순이 되도록 합친다.

3. 비교하고자 하는 배열의 크기가 2 이상일경우에는 두 배열을 합친 크기만큼의 새로운 배열을 만들어준다.

4. 두배열중 가장 작은 수를 새로운 배열의 앞에 넣어준다. 여기서 중요한것은 두 배열은 오름차순으로 정렬이 된 상태 이므로 두배열의 앞만 비교하면 된다.

5-1. 새로운 배열에 넣은 수는 제외하고 다시 비교한다. 그리고 이 과정을 오름차순으로 병합 될때까자 반복한다.

5만 남았으므로 새로운 배열은 1,2,3,5로 정렬이 된다.

5-2. 두 배열의 크기가 맞지 않더라도 위의 과정을 똑같이 거친다.

6. 이런식으로 병합을 하면 오름차순으로 정렬된 배열이 완성 된다.

 

파이썬을 이용한 구현

import sys

def merge_sort(A, p, r):		#병합정렬 함수
    if p < r:				#병합정렬 할 배열의 크기가 1이상인 경우만 그 이후를 실행
        q = int((p+r)/2)		#분해하려는 배열의 중간 선택
        merge_sort(A, p, q)		
        merge_sort(A, q+1, r)		#배열의 크기가 하나가 될때까지 분해
        merge(A, p, q, r)		#그 전까지의 병합정렬이 끝났다면 그 끝난 두 배열에 대해 병합

def merge(A, p, q, r):			#병합하는 함수
    tmp = [0]*(r-p+1)			#두 배열의 크기의 합만큼의 배열 생성
    pp = p						
    qq = q+1
    c = 0
    
    while pp <= q and qq <= r:
        if A[pp] <= A[qq]:
            tmp[c] = A[pp]		#두 배열중 작은 원소끼리 비교 후 작은 원소를 새로운 배열에 저장
            pp += 1			#다음 비교시 제외하고 비교하고자 배열에 넣은 값 다음부터 계산하도록 함
            c += 1
        else:
            tmp[c] = A[qq]		#두 배열중 작은 원소끼리 비교 후 작은 원소를 새로운 배열에 저장
            qq += 1			#다음 비교시 제외하고 비교하고자 배열에 넣은 값 다음부터 계산하도록 함
            c += 1
            
    while pp <= q:			#두 배열중 한 배열에 남은 원소가 있을때 새로 생성했던 배열에 추가(5-2와 같은 상황)
        tmp[c] = A[pp]
        c += 1
        pp += 1
        
    while qq <= r:			#두 배열중 한 배열에 남은 원소가 있을때 새로 생성했던 배열에 추가(5-2와 같은 상황)
        tmp[c] = A[qq]
        c += 1
        qq += 1 
    for i in range(p,r+1):
        A[i] = tmp[i-p]			#정렬된 합친 배열을 두 배열이 위치해 있었던 곳에 다시 저장

num = int(sys.stdin.readline())
A = []
for i in range(num):
    A.append(int(sys.stdin.readline()))
#정렬할 배열 만들기

merge_sort(A, 0, num-1)			#정렬할 배열과 배열의 크기 매개변수로 전달

print(A)