병합 정렬
-
[Python] 병합 정렬(merge sort)Algorithm 2020. 5. 15. 16:47
분할 정복 알고리즘 중 하나로 병합 정렬(merge sort) 또는 합병 정렬이라고 부른다. 정렬되지 않은 전체 데이터를 하나의 단위로 분할한 후 분할한 데이터들을 다시 병합하면서 정렬하는 방식이다. 간단히 설명하자면, 큰 데이터를 하나의 작은 데이터로 쪼갠 후 정렬하면서 다시 합치는 것이다. 시간 복잡도는 O(n*logn)이다. 포인트 1. 분할: 배열이 하나의 원소가 될때 까지 절반으로 나눈다. 2. 병합: 분할된 각각의 원소를 비교하여 정렬된 배열을 만든다. Python Code def mergesplit(data): if len(data) left_point and len(right) > right_point: if left[left_point] > right[right_point]: merged..