merge sort2 5. Array(배열) - Merge Sort(병합정렬) 1. Merge Sort란? - 하나의 배열을 반씩 쪼개어, 배열의 요소를 각각의 배열로 만든다. - 독립적으로 쪼개진 배열을 비교해가며 병합하여 하나의 정렬된 배열을 만드는 알고리즘이다. a) 예제를 통한 병합정렬의 이해 b) 배열간의 요소를 비교하고 병합하는 과정 c) 병합정렬의 시간복잡도 2. 병합정렬 코드구현 # Merge Sort # 1) Merge Sort의 개념 # - 하나의 배열을 반씩 쪼개어 요소의 총 개수만큼 독립된 배열을 만든다. # - 반씩 쪼개진 배열을 Left, Right로 구분한다. # - Left에 있는 배열끼리, Right에 있는 배열끼리의 요소를 비교하여 병합한다. # - 비교 후 병합하는 과정을 반복하여 최종적으로 하나의 정렬된 배열을 만든다. # - 이 과정을 재귀적으.. 2021. 8. 31. Advanced Algorithm - 병합 정렬 (Merge Sort) 1. 병합 정렬이란? - 분할 정복 알고리즘을 기반한 정렬이다. - 재귀용법을 사용한다. a) 병합 정렬의 동작 방식 1. 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 2. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 3. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 2. 어떻게 구현할까? 필요한 기능 1. 단위 데이터까지 나누는 기능 * 단위 데이터: 더 이상 분리될 수 없는 데이터 2. 나눠진 데이터를 정렬하면서 합치는 기능 3. 재귀 용법을 활용하여 1번과 2번 기능을 구현 3. 코드 구현 1) 리스트를 분리하는 기능 def split(data): medium = int(len(data) / 2) #리스트의 중간위치 left = data[:medium].. 2020. 9. 17. 이전 1 다음
