병합 정렬
- 재귀를 사용
- 리스트를 반으로 나눈 후 각 리스트를 합병 정렬을 이용하여 정렬
- 리스트를 나누는 split 함수와 이를 다시 병합하는 merge함수가 필요
split 함수
- 재귀용법을 이용하여 리스트를 반으로 나누는 함수
def split(data):
if len(data) <=1:
return data
medium = int(len(data)/2)
left = split(data[:medium])
right = split(data[medium:])
return merge(left, right)
merge 함수
- left와 right로 나누어진 리스트를 다시 병합하는 함수
- left와 right의 원소가 둘 다 남아있는 경우, left의 원소만 남아있는경우, right의 원소만 남아있는 경우의 세가지 경우를 고려하여 병합한다.
def merge(left, right):
merged=[]
l_point,r_point=0,0
#left/right 원소 모두 존재
while len(left)>l_point and len(right) >r_point:
if left[l_point] > right[r_point]:
merged.append(right[r_point])
r_point+=1
else:
merged.append(left[l_point])
l_point+=1
#left 원소만 있을 때
while len(left)>l_point:
merged.append(left[l_point])
l_point+=1
#right 원소만 있을 때
while len(right)>r_point:
merged.append(right[r_point])
r_point+=1
return merged
병합정렬의 시간복잡도?
-O(nlogn)
728x90
'자료구조 & 알고리즘 & cs > 알고리즘' 카테고리의 다른 글
[TIL] 그래프- 개념 (0) | 2023.03.27 |
---|---|
[TIL] 탐색 알고리즘- 이진 탐색, 순차 탐색 (0) | 2023.03.24 |
[TIL] 동적 계획법 - DP, Dynamic Programming (0) | 2023.03.17 |
[TIL] 퀵정렬 - Quick Sort (0) | 2023.03.15 |
[TIL] 정렬 - Sorting (0) | 2023.03.09 |