728x90
반응형
합병 정렬
: 배열을 좌 우로 나눈 후, 나눈 배열을 정렬하고 다시 붙인다. 퀵 정렬(Quick Sort)과 마찬가지로 재귀 용법을 활용하는 알고리즘이다. 분할 정복 알고리즘 중 하나로, 리스트 길이가 1 이하면 이미 정렬된 것으로 본다.
- 분할 : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 리스트로 만든다.
- 정복 : 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
- 결합 : 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 이 때 정렬 결과가 임시 배열에 저장된다.
- 복사 : 임시 배열에 저장된 결과를 원래 배열에 복사한다.

알게된 개념
1. 리스트 요소 끄집어내기(pop)
-> pop()은 리스트의 맨 마지막 요소를 돌려주고 그 요소는 삭제한다.
>>> a = [1,2,3] >>> a.pop() 3 >>> a [1, 2]
-> pop(x)는 리스트의 x번째 요소를 돌려주고 그 요소는 삭제한다.
>>> a = [1,2,3,4,5] >>> a.pop(1) 2 >>> a [1, 3, 4, 5]
2. 리스트 확장(extend)
-> extend(x)에서 x에는 리스트만 올 수 있으며 원래의 a 리스트에 x 리스트를 더하게 된다.
>>> x = [1,2,3,4,5] >>> x.extend([6,7]) >>> 7 [1, 2, 3, 4, 5, 6, 7] >>> y = [8, 9] >>> x.extend(y) >>> x [1, 2, 3, 4, 5, 6, 7, 8, 9]
x.extend([6,7]]은 x += [6,7]과 동일하다!!!
파이썬으로 구현한 합병 정렬
def merge_sort(arr): if len(arr) <= 1: return arr # divde 과정 mid = len(arr) // 2 left = arr[:mid] right = arr[mid:] # list의 길이가 1이 될 때까지 divide left = merge_sort(left) right = merge_sort(right) return merge(left, right) def merge(left, right): # 복사할 임시 배열 copy = [] # 양쪽 두 리스트 중 하나라도 원소가 없을 때까지 반복. while left and right: if left[0] < right[0]: copy.append(left.pop(0)) else: copy.append(right.pop(0)) # 만약 왼쪽 혹은 오른쪽 리스트가 남았을 때 모두 다 집어넣기 if left: copy.extend(left) elif right: copy.extend(right) return copy arr = [5, 2, 3, 9, 6, 1, 8, 4, 7] print(merge_sort(arr))
728x90
반응형
'Algorithm > Sorting Algorithm' 카테고리의 다른 글
힙 정렬 (Heap Sort) (0) | 2021.07.14 |
---|---|
삽입 정렬 (Insertion Sort) (0) | 2021.07.14 |
퀵 정렬 (Quick Sort) (0) | 2021.07.13 |
선택 정렬 (Selection Sort) (0) | 2021.07.13 |
버블 정렬 (Bubble Sort) (0) | 2021.07.13 |