모두의 알고리즘 문제 10. 병합 정렬

병합정렬의 과정은 다음과 같다.

 

1. 리스트a를 입력으로 받는다.

2. 리스트를 중간을 기준으로 두개로 나누고 각각을 정렬한다.

3. 각 리스트의 첫번째 값을 비교하여 더 작거나, 더 큰 값을 최종 결과 리스트에 집어넣는다.

4. 3번 과정을 두 리스트 중 하나가 모두 빌 때까지 반복한다.

5. 아직 값이 남아있는 리스트의 값들을 전부 최종 결과 리스트에 차례대로 집어 넣는다.

6. 최종 결과 리스트에 정렬된 값이 전부 들어갔으니 이를 반환한다.

 

 

교재에서 쉽게 설명한 병합 알고리즘이다.

 

def merge_sort(a): #리스트a를 입력으로 받음
  n=len(a)

  if n<=1:  #재귀함수를 위한 종료조건. 
    return a   #정렬할 리스트의 자료 개수가 한 개 이하면 정렬할 필요 없음
    
  #그룹을 나누어 각각 병합정렬을 호출
  mid=n//2   # 중간을 기준으로 두 그룹을 나눔
  print(a)
  g1=merge_sort(a[:mid])  #재귀호출로 정렬. a의 0부터 mid직전까지.
  print("g1:",g1)
  g2=merge_sort(a[mid:])  #재귀호출로 정렬. a의 mid부터 끝까지
  print("g2:", g2)
  result=[]  #최종 결과 저장할 리스트
  
  while g1 and g2:  # 두 그룹 모두에 자료가 남아있는한 계속 반복
    
    if g1[0] < g2[0]:  # 두 그룹의 첫번째 값 비교
      result.append(g1.pop(0))
    else:
      result.append(g2.pop(0))

  # 아직 값이 남아있는 그룹의 자료들을 결과에 추가.
  # 비어있는 그룹은 while문 지나친다.
  while g1:
    result.append(g1.pop(0))
  while g2:
    result.append(g2.pop(0))

  return result


d = [6, 8, 3, 2, 1, 9, 4, 5, 10, 7]

print(merge_sort(d))

결과: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

 

 

재귀호출 부분이 트리형인건 알겠는데 어떻게 이뤄지는지 감이 안잡혀서 프린트문을 삽입했다.

 

재귀호출 부분이 어떻게 이뤄지는지 설명하겠다.

 

아래는 print문으로 과정을 재귀호출 과정을 출력한 것인데 이를 이용하여 설명한다.

 

 

 

[6, 8, 3, 2, 1, 9, 4, 5, 10, 7] #정렬할 리스트a. 반으로 나뉘어 g1=[6, 8, 3, 2, 1]과 g2=[9, 4, 5, 10, 7]이 된다.

 

 

[6, 8, 3, 2, 1]  #a를 절반으로 나눈 리스트1. a와 같이 merge_sort를 실행하여 반으로 나뉜다.

[6, 8]  # 리스트1을 절반으로 나눈 리스트1-1, 리스트1의 g1
g1: [6]  # 리스트1-1이 merge_sort를 실행하여 절반으로 나뉨. 값이 1개이므로 그대로 반환.
g2: [8]  # 값이 1개이므로 반환.

 

g1: [6, 8]  #  리스트1-1이 g1, g2를 반환받고 merge_sort의 나머지 과정 실행하여 정렬됨. 리스트1의 g1.

 

[3, 2, 1]  #리스트1을 절반으로 나눈 리스트1-2, 리스트1의 g2
g1: [3]  #리스트 1-2가 반으로 나뉘어 [3], [2, 1]이 됐는데 [3]은 값이 1개이므로 그대로 반환.

 

[2, 1]  #merge_sort 실행
g1: [2]
g2: [1]
g2: [1, 2] # [2, 1]이 merge_sort 실행으로 반으로 나뉜 후 값을 반환받음. 그 후 나머지 과정 실행하여 정렬됨.

g2: [1, 2, 3] # 리스트 1-2가 g1, g2를 전부 반환받았으므로 나머지 과정을 실행하여 값을 정렬함. 리스트1의 g2.

 

 

g1: [1, 2, 3, 6, 8] # 리스트1이 본인의 g1, g2를 반환받아서 나머지 과정을 실행하여 정렬됨.

 

 

[9, 4, 5, 10, 7]  #a를 절반으로 나눈 리스트2

[9, 4]  #리스트 2-1. 리스트2의 g1
g1: [9]
g2: [4]
g1: [4, 9] #리스트 2-1이 본인의 g1, g2를 반환받은 후 정렬됨.

[5, 10, 7]  #리스트2-2. 리스트2의 g2
g1: [5]  #리스트 2-2가 [5], [10, 7]로 나뉨. [5]는 값이 1개이므로 반환.

[10, 7]  # 리스트 2-2의 g2
g1: [10]
g2: [7]
g2: [7, 10] #리스트 2-2의 g2가 정렬 됨.
g2: [5, 7, 10]# 리스트2-2가 본인의 g1, g2를 반환받고 정렬됨

g2: [4, 5, 7, 9, 10] #리스트2가 리스트2-1, 리스트2-2를 반환받고 정렬됨.

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]  #리스트1, 리스트2를 반환받은 리스트a가 정렬됨.

 

 

 

재귀함수의 동작을 다 설명했다. 이제 일반적인 병합 정렬 알고리즘을 작성한다.

def merge_sort(a): #리스트a를 입력으로 받음
  n=len(a)

  if n<=1:  #재귀함수를 위한 종료조건. 
    return a   #정렬할 리스트의 자료 개수가 한 개 이하면 정렬할 필요 없음
    
  #그룹을 나누어 각각 병합정렬을 호출
  mid=n//2   # 중간을 기준으로 두 그룹을 나눔
  g1 = a[:mid]
  g2 = a[mid:]
  merge_sort(g1) #재귀호출로 두 그룹을 정렬
  merge_sort(g2)
  #두 그룹을 하나로 병합
  i1=0  # g1의 원소 번호
  i2=0  # g2의 원소 번호
  ia=0  # 입력받은 리스트a의 원소번호

  while i1 < len(g1) and i2 < len(g2):  # 두 그룹 중 한 그룹이라도 자료가 남아있으면 실행
    if g1[i1] < g2[i2]:  # g1의 원소가 더 작으면
      a[ia] = g1[i1]  #리스트a에 g1의 원소를 덮어씌움
      i1 += 1  #g1 원소번호 1 증가
      ia += 1  #리스트a 원소번호 1 증가
    else:
      a[ia] = g2[i2]  #리스트a에 g2의 원소를 덮어씌움
      i2 += 1  #g2원소번호 1 증가
      ia += 1  #리스트a 원소번호 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, 2, 1, 9, 4, 5, 10, 7]
merge_sort(d)
print(d)

결과: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

 

 

쉽게 표현한 병합정렬과의 차이점을 말하자면, 쉽게 표현한 것은 따로 결과값 집어넣을 변수를 추가하고 이를 반환했지만, 일반적으로 사용하는 병합정렬은 리턴값이 없고 입력한 리스트 안의 자료 순서를 바꿔준다는 것이다.

 

병합정렬은 주어진 문제를 절반으로 나눈 다음 각각을 재귀 호출로 풀어가는 방식이다. 이처럼 큰 문제를 작은 문제로 나눠서 푸는 방법을 알고리즘 설계 기법에서는 '분할 정복(divide and conquer)'이라고 부른다.

 

입력크기가 커서 풀기 어려웠던 문제도 반복해서 잘게 나누다보면 굉장히 쉬운 문제(종료 조건)가 되는 원리를 이용한 것이다. 분할 정복은 잘 활용하면 계산 복잡도가 더 낮은, 효율적인 알고리즘을 만드는데 도움이 된다.

 

분할정복을 이용한 병합정렬의 계산 복잡도는 O(n*logn)으로 선택정렬이나 삽입 정렬의 계산 복잡도 O(n^2)보다 낮다.

 

예를 들면 입력크기가 5천만일 때 n^2은 2500조이고 n*logn은 약 13억이다. 이 사실을 알면 O(n^2) 정렬 알고리즘과 O(n*logn) 정렬 알고리즘의 계산시간이 얼마나 많이 차이 나는지 짐작할 수 있다.