[알고리즘] 병합정렬

1. 병합정렬

- 재귀용법을 활용한 정렬 알고리즘

 - 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.

 - 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.

 - 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

2. 알고리즘 이해

데이터가 네 개 일떄(데이터 갯수에 따라 복잡도가 떨어지는 것은 아니므로, 네 개로 바로 로직을 이해)

예): data_list = [1,9,3,2]

 - 먼저 [1,9],[3,2]로 나누고

 - 다시 앞 부분은 [1], [9]로 나누고

 - 다시 정렬해서 합친다. [1,9]

 - 다음 [3,2]는 [3],[2]로 나누고

 - 다시 정렬해서 합친다. [2,3]

 - 이제 [1,9]와 [2,3]을 합친다.

  - 1<2이니 [1]

  - 9>2이니 [1,2]

  - 9>3이니 [1,2,3]

  - 9 밖에 없으니, [1,2,3,9]

 

3. 알고리즘 구현

mergesplit 함수 만들기

- 만약 리스트 갯수가 한개이면 해당 값 리턴

- 그렇지 않으면 리스트를 앞뒤, 두개로 나누기

- left = mergesplit(앞)

- right = mergesplit(뒤)

merge(left,right)

- 리스트 변수 하나 만들기 (sorted)
  - left_index, right_index = 0
  - while left_index < len(left) or right_index < len(right):
    - 만약 left_index 나 right_index 가 이미 left 또는 right 리스트를 다 순회했다면, 그 반대쪽 데이터를 그대로 넣고, 해당 인덱스 1 증가
    - if left[left_index] < right[right_index]:
      - sorted.append(left[left_index])
      - left_index += 1
    - else:
      - sorted.append(right[right_index])
      - right_index += 1 - 리스트 변수 하나 만들기 (sorted)

 

작은 부분부터 작성해서 하나씩 구현하기

# 어떤 데이터리스트가 있을 때 리스트를 앞뒤로 찌르는 코드 작성해보기
def split_data(data):
	mid = int(len(data)/2)
    left = data[:mid]
    right = data[mid:]
    return left, right
 
 # 재귀용법 활용하기
 def mergesplit(data):
 	if len(data)<=1 :
    	return data
	mid = int(len(data)/2)
    left = mergesplit(data[:mid])
    right = mergesplit(data[mid:])
    return merge(left, right)
    
# merge 함수 작성
def merge(left, right):
	merged = []
    left_point, right_point = 0, 0
 
 # case1 left/right 둘다 있을때
 while len(left) > left_point and len(right) > right_point :
 	if left[left_point] > right[right_point] :
    	merged.append(right[right_point])
        right_point += 1
    else :
    	merged.append(left[left_point])
        left_point += 1
 
 # case2 left 데이터가 없을때
  while len(left) > left_point:
        merged.append(left[left_point])
        left_point += 1
        
 # case3 right 데이터가 없을떄
  while len(right) > right_point:
        merged.append(right[right_point])
        right_point += 1
    
    return merged

import random

data_list = random.sample(range(100), 10)
mergesplit(data_list)

 

4. 알고리즘 분석

알고리즘 분석은 쉽지 않음 - 이부분은 참고

- 몇단계 깊이까지 만들어지는지를 DEPTH라고 하고 i로 놓자. 맨 위 단계는 0으로 놓자

 - 다음 그림에서 n/2^2는 2단계 깊이라고 해보자

 - 각 단계에 있는 하나의 노드 안의 리스트 길이는 n/2^2가 된다.

 - 각 단계에는 2^i개의 노드가 있다.

따라서, 각 단계는 항상 2^i * \frac { n }{ 2^i } = O(n)

단계는 항상 log2n개 만큼 만들어짐, 시간 복잡도는 결국 O(log n), 2는 역시 상수이므로 삭제

따라서 단계별 시간 복잡도 O(n) * O(log n) = O(n log n)