합병정렬2 Merge Sort - 합병 정렬과 코드 병합정렬이라고도 하고 합병정렬이라고도 한다. 합병정렬은 퀵소트와 비슷하면서도 2배의 메모리 공간을 차지한다. 하지만 최선/평균/최악의 경우 시간복잡도가 모두 O(NlogN)으로 같다. 합병정렬은 1. 영역 나누기 2. 각 영역을 Merge Sort 3. 두개의 영역을 Merge 하는 순으로 진행된다. 간단한 예를 그림과 함께 보면 다음과 같다. 배열을 쪼갤 수 있을 때까지 쪼갠후 합친다. 합칠 때는 값을 비교하면서 순서를 맞춰 합친다. 의사코드를 작성해보면 다음과 같다. MergeSort(start, end, arr[], tmp[]){ if(start >= end) return; //분리 mid = (start + end)/2; //합병정렬 MergeSort(start, mid, arr); MergeSo.. 2022. 7. 7. [알고리즘] 병합정렬 알고리즘 | Merge Sort | C++코드 해석 분할정복(Divide and Conquer) 알고리즘을 공부하고있습니다. 병합정렬을 이해해보겠습니다, 우선은 코드는 이렇게 생겼습니다 코드를 이해하기 쉽도록 병합정렬의 개념과 예시그림을 설명하겠습니다! 병합정렬은 분할과 정렬로 나눌수있습니다. 먼저 처음과 끝의 중간에서 두 개로 분할합니다. 이후 분할된 블록들을 계속해서 최소단위까지 분할해줍니다. 8개의 수열을 분할하는 과정을 예로 들면, 이런 식이 됩니다. 코드를 보면 이에 재귀함수를 이용하였는데요, 빨간색 숫자는 재귀함수에 따라 분할이 되는 순서입니다. 재귀함수가 머리아프신분들은 저 순서를 보시면 직관적으로 바로 이해가 되실 거에요! 분할이 끝났으면 5번에서 정렬&병합 한번, 8번에서 한번, 8번 병합이끝나고 6번에 돌아와서 한번, 6번에서 끝나고 2.. 2020. 2. 20. 이전 1 다음
