[5.26] 06-7 병합 정렬

병합 정렬 merge sort - 앞부분, 뒷부분 두 그룹으로 나누어 각각 정렬한 후 병합하는 알고리즘

 

정렬을 마친 배열의 병합

from typing import Sequence

def merge_sorted_list(a:Sequence, b:Sequence) -> None:
  c = [None] * (len(a) + len(b))
  pa, pb, pc= 0, 0, 0
  na, nb = len(a), len(b)

  while pa < na and pb < nb:
    if a[pa] < b[pb]:
      c[pc] = a[pa]
      pa += 1
    else:
      c[pc] = b[pb]
      pb += 1
    pc += 1
  
  while pa < na:
    c[pc] = a[pa]
    pa += 1
    pc += 1

  while pb < nb:
    c[pc] = b[pb]
    pb += 1
    pc += 1
  return c

a = [4, 6, 7, 8, 9]
b = [1, 2, 3, 5, 10]
print(merge_sorted_list(a, b))

예제 코드

from typing import Sequence, MutableSequence

def merge_sorted_list(a:Sequence, b:Sequence, c:MutableSequence) -> None:
  pa, pb, pc= 0, 0, 0
  na, nb, nc = len(a), len(b), len(c)

  while pa < na and pb < nb:
    if a[pa] <= b[pb]:
      c[pc] = a[pa]
      pa += 1
    else:
      c[pc] = b[pb]
      pb += 1
    pc += 1
  
  while pa < na:
    c[pc] = a[pa]
    pa += 1
    pc += 1

  while pb < nb:
    c[pc] = b[pb]
    pb += 1
    pc += 1

if __name__=='__main__':
  a = [2, 4, 5, 6, 7]
  b = [1, 2, 3, 4, 9, 16, 21]
  c = [None] * (len(a) + len(b))

  merge_sorted_list(a, b, c)

  print(f'배열 a: {a}')
  print(f'배열 b: {b}')
  print(f'배열 c: {c}')

#sorted() 함수로 정렬할 수 있다 -> 빠르게 하려면 heapq 모듈의 merge()함수 이용

병합 정렬 만들기

왜 안되는거지..

from typing import Sequence, MutableSequence

def merge_sort(a:MutableSequence) -> None:

  def _merge_sort(a:MutableSequence, left:int, right:int) -> None:
    if left < right:

      center = (left + right) // 2

      _merge_sort(a, left, center)
      _merge_sort(a, center+1, right)

      #지금 하려는 일 = [left:center]와 [center+1:right] 병합하기

      #시작 : pa, pb = 0
      #끝 : na, nb

      pl = 0
      na = center

      pr = center + 1
      nb = right

      pc = 0

      while pl < na and pr < nb:
        if a[pl] >= a[pr]:
          c[pc] = a[pr]
          pr += 1
        else:
          c[pc] = a[pl]
          pl += 1
        pc += 1

      while pl < na:
        c[pc] = a[pl]
        pc += 1
        pl += 1

      while pr < nb:
        c[pc] = a[pr]
        pc += 1
        pr += 1

      a = c
      return a

  n = len(a)
  c = [None] * len(a)
  _merge_sort(a, 0, n-1)

  return a
    
a = [5, 8, 9, 0, 10, 2, 3, 4]
print(merge_sort(a))

 

example

from typing import Sequence, MutableSequence

def merge_sort(a:MutableSequence) -> None:

  def _merge_sort(a:MutableSequence, left:int, right:int) -> None:
    if left < right:

      center = (left + right) // 2

      _merge_sort(a, left, center)
      _merge_sort(a, center+1, right)

      #지금 하려는 일 = [left:center]와 [center+1:right] 병합하기

      #시작 : pa, pb = 0
      #끝 : na, nb

      p = j = 0
      i = k = left

      while i <= center:
        c[p] = a[i]
        p += 1
        i += 1

      while i <= right and j < p:
        if c[j] <= a[i]:
          a[k] = c[j]
          j += 1
        else:
          a[k] = a[i]
          i += 1
        k += 1
      
      while j < p:
        a[k] = c[j]
        k += 1
        j += 1

  n = len(a)
  c = [None] * len(a)
  _merge_sort(a, 0, n-1)

  return a
    
a = [5, 8, 9, 0, 10, 2, 3, 4]
print(merge_sort(a))