[Python Algorithm] 병합정렬 (Divide and Conquer)

 

 

import sys
input = sys.stdin.readline

def Dsort(lt, rt):
  if lt<rt:
    mid = (lt+rt)//2
    Dsort(lt, mid)
    Dsort(mid+1, rt)
    p1 = lt
    p2 = mid+1
    tmp = []
    while p1<=mid and p2<=rt:
      if arr[p1]<arr[p2]:
        tmp.append(arr[p1])
        p1+=1
      else:
        tmp.append(arr[p2])
        p2+=1
    if p1<=mid:
      tmp = tmp + arr[p1:mid+1]
    if p2<=rt:
      tmp = tmp + arr[p2:rt+1]
    for i in range(len(tmp)):
      arr[lt+i] = tmp[i]


arr = [23, 11, 45, 36, 15, 67, 33, 21]
print("Before sort : ", end='')
print(arr)
Dsort(0,7)
print()
print("After sort : ", end='')
print(arr)

 

⭐️ Point ! ⭐️

• 두 영역을 나눔 -> 본연의 일 수행 !
  
  
•  

 

출처

• 인프런 : 파이썬 알고리즘 문제 풀이