힙 정렬이나 합병 정렬을 이용해서 수 정렬하기 문제입니다.
이론상으론 알고있는데 수도코드없이 머리로만 하려니까 에러가 많이 나더라고요...
종이에 적어서 차근차근 풀어보니 쉽게 풀렸습니다.
#include <iostream>
void merge(int* arr, int left, int mid, int right);
void divide(int *arr, int left, int right);
void divide(int *arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
divide(arr, left, mid);
divide(arr, mid+1, right);
merge(arr, left, mid, right);
}
}
void merge(int* arr, int left, int mid, int right) {
int x, y, *newarr;
newarr = new int[right+1];
x = left;
y = mid + 1;
for (int i = left; i <= right; i++) {
if (x > mid) {
while (y <= right) {
newarr[i++] = arr[y++];
}
}
else if (y > right) {
while (x <= mid) {
newarr[i++] = arr[x++];
}
}
else if (arr[x] <= arr[y]) {
newarr[i] = arr[x++];
}
else {
newarr[i] = arr[y++];
}
}
for (int i = left; i <= right; i++) {
arr[i] = newarr[i];
}
delete []newarr;
}
int main() {
int n;
scanf("%d", &n);
int* arr= new int [n+1];
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
divide(arr, 0, n-1);
for (int i = 0; i < n; i++) {
printf("%d\n", arr[i]);
}
scanf("%*d");
}