병합 정렬(Merge sort)

1. 병합 정렬(merge sort)

• 재귀용법을 활용한 정렬 알고리즘
  1. 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
  2. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
  3. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.
     • 크게 Split, Merge 두 단계가 있음

 

2. 알고리즘 이해

• 데이터가 네 개일 때
  • ex : data_list = [1, 9, 3, 2]
    • 먼저 [1, 9][3, 2]로 나눔
    • 다시 앞 부분을 [1], [9]로 나누고
    • 다시 [1, 9]로 정렬해서 합침
    • 뒤도 [3], [2]로 나누고 [2, 3]으로 정렬
    • 이제 [1, 9]와 [2, 3]을 합친다
    • 1 < 2 이므로 [1]
    • 2 < 9 이므로 [1, 2]
    • 9 > 3 이므로 [1, 2, 3]
    • 9만 남아서 [1, 2, 3, 9]로 합쳐짐

 

3. 알고리즘 구현

 

1. Split - 재귀함수 이용

• 리스트 갯수가 1개면 해당 값 리턴
  • 그렇지 않으면 리스트를 앞, 뒤 두 개로 나눔
• left = mergeSplit(앞)
• right = mergeSplit(뒤)
• 후 merge(left, right)

def split(list):
	if len(list) <= 1: return list
    left = list[:데이터 2등분]
    right = list[데이터 2등분:]
    return merge(split(left), split(right))

 

2. Merge

• 리스트 변수 하나 만들기 (sorted)
• left_index, right_index = 0

def merge(left, right):
	if left[lp] < right[rp]: #lp, rp 각각 리스트의 맨 앞 인덱스
    		list.append(left[lp])
        	lp+=1		 #왼쪽 포인터 이동시켜줌
    	else:
    		list.append(right[rp])
        	rp+=1		 #오른쪽 포인터 이동시켜줌
    	return list

 

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

 

분할(Split) 구현

def split(data):
    medium = int(len(data)/2)
    left = data[:medium]
    right = data[medium:]
    print(left, right)

 

분할/합병 구현

def mergesplit(data):
    if len(data)<=1:
        return data
    medium = int(len(data)/2)
    left = mergesplit(data[:medium])
    right = mergesplit(data[medium:])
    return merge(left, right)

def merge(left, right):
    merged = list()
    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:
            merge.append(left[left_point])
            left_point+=1

    #case2: left만 남아있을 때
    while len(left) > left_point:
        merge.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, 7, 16, 24, 33, 47, 56, 76, 90, 97]

 

4. 알고리즘 분석

• 알고리즘 분석이 쉽지 않다
  • 몇 단계 깊이까지 만들어지는를 depth라 하고 i로 가정. 맨 위 단계는 0
    • 다음 그림에서 n/2^2는 2단계 깊이라고 가정
    • 각 단계에 있는 하나의 노드 안의 리스트 길이는 n/2^2가 된다
    • 각 단계에는 2^i개의 노드가 있다
  • 따라서 각 단계는 항상 2^i * n/2^i = O(n)
  • 단계는 항상 log2n개 만큼 만들어짐, 시간 복잡도는 결국 O(log n), 2는 역시 상수이므로 삭제
  • 따라서 단계별 시간 복잡도 O(n) * O(log n) = O(n log n)