파이썬으로 bottom-up 방식 merge sort 구현하기
1. merge sort란?
합병정렬/병합정렬은 반씩 분할해서 다시 합치면서 정렬하는 방식이다.
https://ko.wikipedia.org/wiki/합병_정렬#/media/파일:Merge-sort-example-300px.gif
2. merge sort in python
이를 python3에서 구현하면 다음과 같다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | # merge sort def merge(left, right) : v=list() i=0;j=0 while(i<len(left) and j<len(right)) : if left[i]<=right[j] : v.append(left[i]) i+=1 else : v.append(right[j]) j+=1 if i==len(left) : v = v + right[j:len(right)] if j == len(right): v = v + left[i:len(left)] return v def merge_sort(v) : if len(v) <= 1 : return v m = len(v)//2 left = merge_sort(v[0:m]) right = merge_sort(v[m:len(v)]) return merge(left, right) | cs |
merge_sort() 에서 list를 반으로 계속 분할하고, merge() 에서 분할된 두 list를 순서대로 정렬하면서 합친다.
* merge() 예시
> left = [1, 2, 5, 7, 8]
> right = [0, 3, 4, 6, 9]
> merge(left, right)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
ㅁ : left/ ㅁ : right
left list에 1과 right list에 0 중 0이 더 작기 때문에 0을 return할 list에 집어넣고, right list의 j 인덱스는 하나 더해준다.
위와 같은 방법으로 1과 3 중에는 1이 더 작기 때문에 1을 return할 list에 넣고, i 인덱스는 하나 더해준다.
이를 right와 left list 중 하나가 다할 때 까지 반복한다.
이후 return할 list와 남은 list 요소들을 합해준다.
* merge_sort() 예시
> merge_sort([0, 5, 7, 6, 1, 2, 8, 3, 4, 9])
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
input으로 들어간 10개의 요소로 이루어진 list는 5:5로 분해된다.
5:5로 분해된 요소는 다시 반으로 분해된다.
결국 하나의 요소만 남았을 때 return하고, return된 left 요소와 right요소들은 merge(left, right)에서 정렬되면서 합쳐진다.
'코딩테스트 연습 > Python' 카테고리의 다른 글
[알고리즘] 파이썬으로 힙 정렬 구현하기 :: heap sort in python (2) | 2019.11.10 |
---|---|
[알고리즘] 파이썬으로 삽입정렬 구현하기 :: insertion sort in python (0) | 2019.11.07 |
[알고리즘] 파이썬으로 거품정렬 구현하기 :: bubble sort in python (0) | 2019.11.06 |
[알고리즘] 파이썬으로 sort하기 :: bubble sort(버블정렬), insert sort(삽입정렬), merge sort(병합정렬), heap sort(힙정렬) (0) | 2019.11.05 |
[python] 소수 찾기 - 에라토스테네스의 체 (0) | 2019.09.25 |