병합 정렬
#include <iostream>
using namespace std;
int temp[6];
int arr[] = { 4, 2, 6, 1, 5, 3 };
void merge(int start, int end) {
int mid = (start + end) / 2;
int i = start, j = mid + 1, k = start;
while (i <= mid && j <= end) {
if (arr[i] <= arr[j]) {
temp[k] = arr[i];
i++;
}
else {
temp[k] = arr[j];
j++;
}
k++;
}
if (i > mid) { //i가 먼저 데이터를 모두 넣어서 j가 남았을 경우
for (int a = j; a <= end; a++) {
temp[k] = arr[a];
k++;
}
}
else { //j가 먼저 데이터를 모두 넣어서 i가 남았을 경우
for (int a = i; a <= mid; a++) {
temp[k] = arr[a];
k++;
}
}
for (int a = start; a <= end; a++) //정렬된 배열을 원래의 배열에 복사
arr[a] = temp[a];
}
void merge_sort(int start, int end) {
if (start >= end) // 개수가 1개일 때
return;
int mid = (start + end) / 2;
merge_sort(start, mid);
merge_sort(mid + 1, end);
merge(start, end);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
merge_sort(0, 5);
for (int i = 0; i<6; i++) {
cout << arr[i] << ' ';
}
return 0;
}
시간 복잡도: O(NlogN)
'알고리즘 > C++' 카테고리의 다른 글
[알고리즘] 이분 탐색 (0) | 2023.10.01 |
---|---|
[알고리즘] 탐욕(그리디) 알고리즘 (0) | 2021.11.01 |
[알고리즘] 퀵 정렬 - C++ (0) | 2021.09.22 |
[알고리즘] 삽입 정렬 - C++ (0) | 2021.09.22 |
[알고리즘] 선택 정렬 - C++ (0) | 2021.09.22 |
댓글