TIL 1일차

합병 정렬(merge sort) 알고리즘의 구체적인 개념

하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.

 

---

 

합병 정렬은 다음의 단계들로 이루어진다.

분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다. 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다.

 

결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.

 

---

 

합병 정렬의 과정

추가적인 리스트가 필요하다. 각 부분 배열을 정렬할 때도 합병 정렬을 순환적으로 호출하여 적용한다. 합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병(merge)하는 단계 이다.

 

합병 정렬(merge sort) 알고리즘의 특징

단점 만약 레코드를 배열(Array)로 구성하면, 임시 배열이 필요하다.

 

제자리 정렬(in-place sorting)이 아니다. 레코드들의 크기가 큰 경우에는 이동 횟수가 많으므로 매우 큰 시간적 낭비를 초래한다.

 

장점 안정적인 정렬 방법 데이터의 분포에 영향을 덜 받는다.

 

즉, 입력 데이터가 무엇이든 간에 정렬되는 시간은 동일하다. (O(nlog₂n)로 동일) 만약 레코드를 연결 리스트(Linked List)로 구성하면, 링크 인덱스만 변경되므로 데이터의 이동은 무시할 수 있을 정도로 작아진다.

 

제자리 정렬(in-place sorting)로 구현할 수 있다. 따라서 크기가 큰 레코드를 정렬할 경우에 연결 리스트를 사용한다면, 합병 정렬은 퀵 정렬을 포함한 다른 어떤 졍렬 방법보다 효율적이다.

 

 

import sys

input = sys.stdin.readline
output = sys.stdout.write

list = [20,10,70,80,40,90]

def merge(list,left,mid,right):
  blist = [0] * 100
  i = left
  j = mid + 1
  k = 0
  
  # 본격적으로 시작
  while i <= mid and j <= right:
    if list[i] <= list[j]:
      blist[k] = list[i]
      k+= 1
      i+= 1
    else:
      b[k] = list[j]
      j += 1
      k += 1
  # 왼쪽이 남아있는지
  while i <= mid:
    blist[k] = list[i]
    k += 1
    i += 1
  # 오른쪽이 남아있는지
  while j <= right:
    blist[k] = list[j]
    j += 1
  # 문서작성
  k -= 1
  while k >= 0:
    list[low + k] = blist[k]
    k -= 1
    
def mergesort(list,left,right) :
  if left < right:
    m = left+(right-1) / 2
    mergesort(list,left,m)
    mergesort(list,m+1,right)
    merge(list,left,m,right)

mergesort(list,0,len(list)-1)

 

---

 

합병 정렬의 시간복잡도

 

합병 정렬은 무조건 절반으로 divide 하는 과정과 n개의 갯수만큼 combine 하는 과정을 겪으므로 

 

O(nlon n)를 보장해주는 아주 강력한 알고리즘이다.