차밍이
[알고리즘] 패스트캠퍼스 알고리즘 학습 - 병합 정렬(Merge Sort) 본문
반응형
1. 정의
재귀 용법을 활용한 정렬 알고리즘
- 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
- 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
- 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.
2. 알고리즘 이해
이해를 돕기위한 예시
쪼개는 단계 [1, 9, 3, 2]
> [1, 9]
, [3, 2]
> [1]
, [9]
, [3]
, [2]
더 이상 쪼갤 수 없으면 합병을 진행
작은 데이터를 앞에 큰 데이터를 뒤로 가도록 병합한다.
[1]
, [9]
, [3]
, [2]
> [1, 9]
, [2, 3]
> [1, 2, 3, 9]
왼쪽 index 번호와, 오른쪽 index 번호를 활용해서 값을 비교해서 넣어가는 방식으로 진행하면 된다.
3. 코드 작성
데이터를 나누는 부분 & 데이터를 합치는 부분
크게 두 개의 함수로 구성될 것을 생각할 수 있다.
def merge(left, right):
left_idx, right_idx = 0, 0
sorted_list = []
left_len, right_len = len(left), len(right)
while(left_len > left_idx and right_len > right_idx):
if left[left_idx] <= right[right_idx]:
sorted_list.append(left[left_idx])
left_idx += 1
else:
sorted_list.append(right[right_idx])
right_idx += 1
while(left_len > left_idx):
sorted_list.append(left[left_idx])
left_idx += 1
while(right_len > right_idx):
sorted_list.append(right[right_idx])
right_idx += 1
return sorted_list
def mergeSplit(data_list):
if len(data_list) <= 1:
return data_list
length = len(data_list)
mid = length//2
left = split(data_list[:mid])
right = split(data_list[mid:])
return merge(left, right)
## 결과 검증
import random
rand_list = random.sample(range(100), 10)
print(mergeSplit(rand_list))
print(mergeSplit([1, 9, 4, 8, 2, 4, 5, 11]))
>>>
[17, 25, 40, 45, 50, 56, 64, 73, 84, 89]
[1, 2, 4, 4, 5, 8, 9, 11]
[알고리즘] 패스트캠퍼스 알고리즘 학습 - 퀵 정렬(Quick Sort)
[알고리즘] 패스트캠퍼스 알고리즘 학습 - 삽입 정렬(Insertion Sort)
[알고리즘] 패스트캠퍼스 알고리즘 학습 - 선택 정렬(Selection Sort)
반응형
'파이썬 > 알고리즘' 카테고리의 다른 글
[Python] 백준 1325번 효율적인 해킹 - BFS로 탐색하는 노드 수 카운트 (2) | 2022.04.12 |
---|---|
[Python] 백준 1697번 숨바꼭질 - 차근차근 문제접근 (0) | 2022.04.11 |
[Python] 백준 2164번 카드2 - deque (1) | 2021.07.25 |
[파이썬] 백준 11047번 : 동전 0 - 알고리즘 문제풀이 (0) | 2021.06.26 |
[알고리즘] 패스트캠퍼스 알고리즘 학습 - 퀵 정렬(Quick Sort) (0) | 2021.04.07 |
[알고리즘] 패스트캠퍼스 알고리즘 학습 - 동적 계획법과 분할 정복 with 피보나치 (0) | 2021.04.06 |
[알고리즘] 패스트캠퍼스 알고리즘 학습 - 선택 정렬(Selection Sort) (0) | 2021.04.03 |
[알고리즘] 패스트캠퍼스 알고리즘 학습 - 버블정렬 (0) | 2021.04.01 |
관련된 글 보기
Comments