# 합병 정렬 특징 1. 분할 정복 알고리즘 2. 동일한 원소 존재시, 원래의 순서를 보존하는 안정 정렬 3. 일반적으로 최고, 최악, 평균 시간 복잡도 O(N * logN) 4. 임시 버퍼의 필요로 공간 복잡도 O(N) 알고리즘 1. 입력 버퍼를 절반씩 분할하여 나눈 두 버퍼에 대해 각 재귀함수를 호출 2. 계속 나누면서 들어가다가, 버퍼의 크기가 1일 때 중단점을 걸어 반환 3. 재귀함수를 나오면서 두 버퍼의 첫 요소부터 비교하여 작은 요소부터 임시 버퍼에 복사 (복사한 요소는 더이상 비교 대상이 아니며, 해당 버퍼의 index는 1 증가) 4. 복사한 구간의 임시 버퍼를 입력 버퍼에 복사 구현 및 상세 설명 #include void sort(std::vector& buf) { std::vector ..
[C++] 병합 정렬 (Merge sort) 개념 및 구현
# 합병 정렬 특징 1. 분할 정복 알고리즘 2. 동일한 원소 존재시, 원래의 순서를 보존하는 안정 정렬 3. 일반적으로 최고, 최악, 평균 시간 복잡도 O(N * logN) 4. 임시 버퍼의 필요로 공간 복잡도 O(N) 알고리즘 1. 입력 버퍼를 절반씩 분할하여 나눈 두 버퍼에 대해 각 재귀함수를 호출 2. 계속 나누면서 들어가다가, 버퍼의 크기가 1일 때 중단점을 걸어 반환 3. 재귀함수를 나오면서 두 버퍼의 첫 요소부터 비교하여 작은 요소부터 임시 버퍼에 복사 (복사한 요소는 더이상 비교 대상이 아니며, 해당 버퍼의 index는 1 증가) 4. 복사한 구간의 임시 버퍼를 입력 버퍼에 복사 구현 및 상세 설명 #include void sort(std::vector& buf) { std::vector ..
2023.11.27