✅ std::sort()는 Introsort 사용
✅ mergeSort()는 항상 O(N log N)
정렬 방법 평균 시간 복잡도 최악의 경우 추가 메모리 사용
🚀 std::sort() (Introsort) | O(N log N) | O(N log N) | O(1) (제자리 정렬) |
🚀 mergeSort() (합병 정렬) | O(N log N) | O(N log N) | O(N) (배열 복사 필요) |
#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
using namespace std;
using namespace chrono;
// 두 개의 정렬된 배열을 병합하는 함수
void merge(vector<int>& arr, int left, int mid, int right) {
vector<int> temp;
int i = left, j = mid + 1;
while (i <= mid && j <= right) {
if (arr[i] < arr[j]) temp.push_back(arr[i++]);
else temp.push_back(arr[j++]);
}
while (i <= mid) temp.push_back(arr[i++]);
while (j <= right) temp.push_back(arr[j++]);
for (int k = left; k <= right; k++) arr[k] = temp[k - left];
}
// 합병 정렬 (Merge Sort)
void mergeSort(vector<int>& arr, int left, int right) {
if (left >= right) return;
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
int main() {
const int N = 1000000; // 배열 크기
vector<int> arr1(N), arr2(N);
// 랜덤 데이터 생성
for (int i = 0; i < N; i++) arr1[i] = arr2[i] = rand();
// ✅ std::sort() 실행 시간 측정
auto start = high_resolution_clock::now();
sort(arr1.begin(), arr1.end());
auto end = high_resolution_clock::now();
cout << "std::sort() 실행 시간: " << duration<double>(end - start).count() << " 초\n";
// ✅ mergeSort() 실행 시간 측정
start = high_resolution_clock::now();
mergeSort(arr2, 0, N - 1);
end = high_resolution_clock::now();
cout << "mergeSort() 실행 시간: " << duration<double>(end - start).count() << " 초\n";
return 0;
}
(컴퓨터 성능에 따라 다를 수 있음)
std::sort() 실행 시간: 0.27 초
mergeSort() 실행 시간: 0.85 초
✅ 결론:
상황 어떤 정렬을 선택?
🚀 메모리를 아끼고 싶다 | std::sort() 사용! (제자리 정렬, O(1) 메모리) |
🚀 안정적인 정렬이 필요하다 (Stable Sort) | mergeSort() 사용! (순서 유지 가능) |
🚀 최악의 경우에도 O(N log N) 성능 보장 | mergeSort() 사용! |
🚀 빠른 정렬이 필요하다 | std::sort() 사용! (일반적으로 더 빠름) |
✅ 🚀 std::sort()가 더 빠르고 효율적이므로 기본적으로 std::sort()를 사용하자!
✅ 🚀 하지만, "안정 정렬(Stable Sort)"이 필요하다면 mergeSort()를 사용할 수 있다.
분할 정복(Divide and Conquer) (0) | 2025.03.03 |
---|---|
분할 정복 : 이진 탐색 (Binary Search) (0) | 2025.03.02 |
분할정복 :합병 정렬 (Merge Sort) (0) | 2025.03.02 |
트리 순회(Tree Traversal) 방법 02 : 코드 (0) | 2025.03.02 |
🚀 트리 순회(Tree Traversal) 방법 : 후위, 전위, 중위, 레벨 (0) | 2025.03.02 |