자료구조&알고리즘

[알고리즘] 병합 정렬 merge sort

파송송 2022. 10. 28. 16:00
728x90

병합 정렬 (합병 정렬) merge sort

  • 동적 프로그래밍과 달리 memorization 방법은 쓰지 않고 재귀용법을 씀
  • 분할정복 알고리즘을 사용한 정렬 알고리즘 중 하나임
    • 리스트를 절반으로 잘라 비슷한 크기의 두 리스트로 나눈다. ( 리스트를 자르는 함수)
    • 각 부분 리스트를 재귀적 합병 정렬을 이용하여 정렬한다.
    • 두 부분의 리스트를 다시 하나의 정렬된 리스트로 합병한다.

https://visualgo.net/en/sorting

 

Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgo

VisuAlgo is free of charge for Computer Science community on earth. If you like VisuAlgo, the only "payment" that we ask of you is for you to tell the existence of VisuAlgo to other Computer Science students/instructors that you know =) via Facebook/Twitte

visualgo.net


이해


코드

  • split, merge 함수가 필요함
def merge(left, right):
    merged = list()
    lp, rp = 0, 0 #index 번호

    
    #case1: left, right에 값이 있을 때
    while len(left) > lp and len(right) > rp :
        if left[lp] > right[rp]:
            merged.append(right[rp])
            rp += 1
        else:
            merged.append(left[lp])
            lp += 1
    
    #case2: left만 남음
    while len(left) > lp:
        merged.append(left[lp])
        lp += 1
        
    #case3 : right만 남음
    while len(right) >rp:
        merged.append(right[rp])
        rp += 1
            
    return merged
    
    ---------------------------------------------------------------------------------
    
   def merge_sort(data):
    if len(data)<=1:
        return data
    medium = int(len(data)/2)
    left = merge_sort(data[:medium])
    right = merge_sort(data[medium:])
    return merge(left, right
import random

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

merge_sort(data_list)
[31, 34, 66, 69, 91] [0, 4, 48, 82, 86]
[0, 4, 31, 34, 48, 66, 69, 82, 86, 91]

시간복잡도

list 나누기

단계에 있는 노드 list의 길이는 \( \frac {n} {2^{n}} \) 이 되고 노드는 \( 2^{n} \) 개가 된다.

이때 시간 복잡도는  \( 2^{n} \) * \( \frac {n} {2^{n}} \) 로 \( O(n)  \) 이 된다

 

list 병합

단계는 \( log_{2}n \)개 만들어진다 \( O(log(n) \)

 

merge sort의 시간 복잡도는 \( O(n log n) \) 이다

 

728x90