Python의 병합 정렬 설명

병합 정렬은 정렬 기술입니다. 시간 복잡도가 (n logn인 효율적인 정렬 알고리즘입니다. ) 여기서 n은 정렬할 배열의 길이입니다.

병합 정렬은 분할 및 정복 패러다임을 따르는 알고리즘입니다. 어레이를 두 개의 동일한 반으로 계속 나눕니다. 나중에 각각 단일 요소가 있는 목록을 정렬하기 시작하고 정렬된 목록을 연속적으로 병합하여 완전한 정렬된 목록을 형성합니다.

따라서 정렬된 배열을 얻습니다.

예

보라색 상자와 검은색 화살표는 목록을 두 부분으로 나누는 것을 보여줍니다.

녹색 상자와 빨간색 화살표는 정렬된 두 목록의 병합을 보여줍니다.

병합 정렬 구현

목록을 두 부분으로 나누는 것은 매우 쉽고 요소가 하나만 남을 때까지 재귀적으로 수행됩니다. 나중에 병합 절차가 수행되며 실제로 두 개의 정렬된 목록을 병합하는 논리를 적용합니다.

예시

merge 함수는 병합될 두 개의 정렬된 배열을 취합니다. a1의 맨 앞 요소는 a2의 맨 앞 요소와 비교됩니다. 둘 중 가장 작은 것이 목록 c에 추가되고 해당 배열의 포인터가 증가합니다.

def merge(a1,a2):
   c=[]
   x=0
   y=0
   while(x<len(a1) and y<len(a2)):
      if(a1[x]<a2[y]):
         c.append(a1[x])
         x+=1
      else:
         c.append(a2[y])
         y+=1
   while(x<len(a1)):
      c.append(a1[x])
      x+=1
   while(y<len(a2)):
      c.append(a2[y])
      y+=1
   return c

def mergesort(array):
   if(len(array)==1):
      return array
   mid=(len(array))//2
   a1=mergesort(array[:mid])
   a2=mergesort(array[mid:])
   return merge(a1,a2)
array=[2,3,1,5,4,6,8,10,7,9]
print(mergesort(array))

출력

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