[4.14] 문제 10. 병합 정렬로 줄 세우기

모두의 알고리즘 with 파이썬

 

문제 10. 병합 정렬

 

쉽게 설명한 병합 정렬 알고리즘

def merge_sort(a):
  n = len(a)
  if n <= 1:
    return a
  mid = n // 2
  g1 = merge_sort(a[:mid])
  g2 = merge_sort(a[mid:])
  result = []
  while g1 and g2:
    if g1[0] < g2[0]:
      result.append(g1.pop(0))
    else:
      result.append(g2.pop(0))
  while g1:
    result.append(g1.pop(0))
  while g2:
    result.append(g2.pop(0))
  return result

d = [6, 8, 9, 5, 4, 3, 1]
print(merge_sort(d))

일반적인 병합 정렬 알고리즘

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, 9, 10, 8, 5, 4, 3, 1, 2, 7]
merge_sort(d)
print(d)

알고리즘 분석

divide and conquer -> O(nlogn)

재귀호출 관계

병합 정렬하는 과정

a = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5] 대입 ? 

merge_sort(a)

g1 = [3, 6, 8, 9, 10]

g2 = [1, 2, 4, 5, 7]

r = []

while g1 and g2:

- g1[0] > g2[0] 

result = g2.pop(0)

g1 = [3, 6, 8, 9, 10]

g2 = [2, 4, 5, 7]

r = [1]

- g1[0] > g2[0]

result = g2.pop(0)

g1 = [3, 6, 8, 9, 10]

g2 = [4, 5, 7]

r = [1, 2]

- g1[0] < g2[0]

result = g1.pop(0)

g1 = [6, 8, 9, 10]

g2 = [4, 5, 7]

r = [1, 2, 3]

- g1[0] > g2[0]

result = g2.pop(0)

g1 = [6, 8, 9, 10]

g2 = [5, 7]

r = [1, 2, 3, 4]

- g1[0] > g2[0]

result = g2.pop(0)

g1 = [6, 8, 9, 10]

g2 = [7]

r = [1, 2, 3, 4, 5]

- g1[0] < g2[0]

result = g1.pop(0)

g1 = [8, 9, 10]

g2 = [7]

r = [1, 2, 3, 4, 5, 6]

- g1[0] > g2[0]

result = g1.pop(0)

g1 = [8, 9, 10]

g2 = []

r = [1, 2, 3, 4, 5, 6, 7]

while g1:

result.append(g1.pop(0))

r = [1, 2, 3, 4, 5, 6, 7, 8]

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

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

return r