병합정렬은 분할정복 알고리즘의 가장 좋은 예이다.
정렬할 리스트를 반으로 나누어 두 부분을 따로 정렬하여 다시 조합하는 과정이다.
시간복잡도는 O(n*log n)
def merge_sorted(arr):
if len(arr)>1:
mid = len(arr)//2
left = arr[:mid]
right = arr[mid:]
l = merge_sorted(left)
r = merge_sorted(right)
return merge(l, r)
else:
return arr
def merge(left, right):
i = 0
j = 0
arr = []
while (i<len(left)) & (j<len(right)):
if left[i] < right[j]:
arr.append(left[i])
i+=1
else:
arr.append(right[j])
j+=1
#ㅇㅇㅇ
while (i<len(left)):
arr.append(left[i])
i+=1
#
while (j<len(right)):
arr.append(right[j])
j+=1
return arr
arr = [3, 5, 1, 2, 9, 6, 4, 5, 7]
print(merge_sorted(arr))
'아카이빙' 카테고리의 다른 글
Python으로 알고리즘 공부 06. 소수 (Prime number) (0) | 2017.07.05 |
---|---|
Python으로 알고리즘 공부 05. 퀵 셀렉션 (Quick Selection) (0) | 2017.07.05 |
Python으로 알고리즘 공부 04. 이진 검색 (Binary Search) (0) | 2017.07.05 |
Python으로 알고리즘 공부 03. 계수 정렬 (Counting Sort) (0) | 2017.07.03 |
Python으로 알고리즘 공부 02. 퀵 정렬 (Quick Sort) (0) | 2017.07.03 |