10병합 정렬
◼︎ 10-1 내림차순 병합 정렬
오름차순 정렬에서 값을 비교하는 부분(g1[i1] < g2[i2])의 부등호 방향을 반대로 하면 내림차순 정렬 프로그램이 됩니다.
◉ 예제 소스 e10-1-msort.py
# 내림차순 병합 정렬
# 입력: 리스트 a
# 출력: 없음(입력으로 주어진 a가 정렬됨)
def merge_sort(a):
n = len(a)
# 종료 조건: 정렬할 리스트의 자료 개수가 한 개 이하이면 정렬할 필요가 없음
if n <= 1:
return
# 그룹을 나누어 각각 병합 정렬을 호출하는 과정
mid = n // 2
g1 = a[:mid]
g2 = a[mid:]
merge_sort(g1)
merge_sort(g2)
# 두 그룹을 합치는 과정(병합)
i1 = 0
i2 = 0
ia = 0
while i1 < len(g1) and i2 < len(g2):
if g1[i1] > g2[i2]: # 부등호 방향 뒤집기
a[ia] = g1[i1]
i1 += 1
ia += 1
else:
a[ia] = g2[i2]
i2 += 1
ia += 1
while i1 < len(g1):
a[ia] = g1[i1]
i1 += 1
ia += 1
while i2 < len(g2):
a[ia] = g2[i2]
i2 += 1
ia += 1
d = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]
merge_sort(d)
print(d)
◉ 실행 결과
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]