728x90

O(n*logn)의 성능을 나타내는 병합정렬(합병정렬)을 파이썬으로 구현할 것이다.
병합정렬
힙정렬, 퀵정렬만큼 빠른 정렬 알고리즘이다.
병합정렬은 크게 분할과 병합과정으로 나누어진다.
과정 요약
배열의 모든 원소들을 하나씩 분할한 후, 각 원소들끼리 비교하며 다시 병합하는 과정을 거친다.
과정
1. 배열을 하나씩 분해할때 까지 분해한다.

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

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

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

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


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)반응형
'알고리즘 > 알고리즘' 카테고리의 다른 글
| 모듈러 연산 (0) | 2023.10.15 |
|---|---|
| [알고리즘] 이항 계수 (0) | 2023.10.08 |
| [알고리즘] 소수 구하기 (아리토스테네스의 체) (0) | 2023.09.25 |
| [알고리즘] 최대공약수, 최소공배수 (유클리드 호제법) (0) | 2023.09.23 |
| [알고리즘] Heap sort :: 힙 정렬 (0) | 2023.01.04 |