728x90
반응형
정렬
-
[알고리즘] 정렬 알고리즘 : 합병정렬 (Merge sort)CS기초/Algorithm, Data Structures 2023. 6. 27. 08:19
정렬의 기초로 분할 정복 방법을 사용해 분할, 정복, 결합의 세 단계를 거친다. 분할: 배열을 동일한 크기의 두 개의 부분 배열로 분할한다. 입력 크기를 n이라고 한다면 분할된 부분배열의 크기는 n/2가 된다. 정복: 각각의 부분 배열에 대해 합병 정렬을 순환적으로 적용한다. 결합: 정렬된 두 부분 배열을 합쳐서 하나의 정렬된 배열을 만든다. 간단하게 설명하면 합병정렬은 배열을 쪼개서 각각 정렬한 후 합치는 알고리즘이다. def merge_sort(num): l = len(num) if l > 1: mid = round(l/2+0.1) left = merge_sort(num[:mid]) right = merge_sort(num[mid:]) num = merge(left, right, mid, l-mid)..