개발 공부/Algorithm
Merge Sort (합병 정렬) python으로 구현하기
뺙사우르수
2020. 3. 16. 18:04
728x90
- Merge Sort 설명
✔ divide & conquer방법을 이용함
✔ n개의숫자들을 반으로 나눠 2개의 부분으로 분할하고 → 각각의 부분을 재귀적으로 정렬한 후 → 2개의 정렬된 부분을 merge하여 정렬
- Mergesort
(1) 1개의 정렬되지 않은 배열을 2개의 배열로 분할하는것을 반복 → 배열의 원소 갯수가 1개가 될때까지 반복
(2) 양쪽의 배열의 크기가 둘 다 1개가 되면 merge시켜준다
✔ 입력 크기가 n=6 , list A= [ 9, 20, 5, 15, 3, 11 ]인 경우

초록색 화살표는 divide하는 과정, 노란색 화살표는 merge하는 과정을 의미한다.
- Merge
✔ 두개의 정렬된 배열을 하나의 정렬된 배열로 합치는 function
✔ A=[1,,,,h] 와 B=[1,,,,m]을 merge하여 S=[1,,,,,h+m] 으로 합친다

< 순서 >
(1) i, j=0부터 시작한다
(2) A[i], A[j]값을 비교해서 작은 값을 list S에 넣어준다.
(3) 작은 값의 index를 1개 증가해줄것 (i+=1 or j+=1)
- python code (Merge)

- python code (MergeSort)

728x90