정렬1 병합 정렬(Merge Sort) (참고) 폰 노이만이 고안 QSort, MSort 둘 다 Divide & Conquer 철학에서 나온 것 머지소트는 많은 자료를 한번 정렬하는 것보다 적은 자료를 여러 번 정렬하겠다는 철학에서 나옴 Q M 전략 Pivot 기준 절반 무조건 절반 Avg O(nlogn) O(nlogn) Worst O(n2) O(nlogn) 공간 자료 공간 자료 공간 * 2 1. 영역 나누기 2. 각 영역 재귀적 진행 3. 두 개의 영역 Merge -Merge 과정 (S,m) (m+1,e) 두개의 영역을 -> (S,e) 배열로 넣는다. Idx1, idx2를 이용해 우선순위인 것을 먼저 넣어주고 그 쪽 인덱스를 ++ 한쪽이 끝나면 나머지를 전부다 넣어준다. void msort(int s, int e) { int l, r, t,.. 2019. 11. 17. 이전 1 다음