자료구조 & 알고리즘/알고리즘
[고급정렬 ]: 병합정렬
쉽코기
2021. 9. 16. 15:57
병합 정렬(merge sort) 알고리즘 핵심
- 안정 정렬에 속하며 대표적인 분할정복 알고리즘중 하나이다.
- 분할정복이란?
- 분할정복은 일반적으로 재귀 호출을 사용한다.
- devide : 문제를 한개 또는 둘 이상으로 나눈다
- conquer : 나누어진 문제가 충분히 작고 해결 가능하다면 해결한다.
- devide 와 conquer 를 반복하며 결과를 합쳐서 문제를 해결한다
- 과정
- 리스트의 길이가 1일때 가지 두개로 양분하여 분할한다. (재귀 호출)
- 길이가 충분해졌다면 해당 리스트들을 정렬하여 합친다.
- 시간복잡도
- O(nlogn) 을 갖게된다.
- 분할정복이란?
병합 정렬(merge sort) 예제 코드(파이썬)
# 병합정렬
def splite_merge(lst:list):
if len(lst) < 2:
return lst
else:
lenght = len(lst)//2
left , right = lst[:lenght] ,lst[lenght:]
return merge(splite_merge(left) , splite_merge(right))
def merge (right , left):
right_cnt , left_cnt = 0, 0
lst = []
while (left_cnt < len(left) and right_cnt < len(right)):
if right[right_cnt] < left[left_cnt]:
lst.append(right[right_cnt])
right_cnt += 1
else:
lst.append(left[left_cnt])
left_cnt += 1
if left_cnt != len(left) :
lst.extend(left[left_cnt:])
else :
lst.extend(right[right_cnt:])
return lst
import random
lst = random.sample(range(50) , 40)
#print(lst)
print(splite_merge(lst))