[C] 백준 2751번 : 수 정렬하기 2

www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

---

문제 접근

 1. 만들어둔 배열에 숫자를 입력 받는다.

 2. 입력받은 값들을 잘게 자른다. 이 때, 재귀를 이용한다.

 3. 값을 비교해서 작은 값 순서대로 새로운 배열에 담아둔다.

 4. 값이 모두 정렬되면 기존의 배열에 새로 담는다.

느낀점

합병 정렬이라는 알고리즘을 수업시간에 배우긴 했지만 직접 코드를 구성하는건 이번이 처음이었다. 문제에서 너무 어려운 알고리즘이니 내장 정렬 함수를 사용하라곤 했지만 이번 기회에 공부하는 셈치고 했다. 하지만 내장 정렬 함수를 공부하는게 더 나았을 것 같다.

코드

#include <stdio.h>

void merge(int list[], int left, int mid, int right) {
    int sorted[1000000];
    int i, j, k, l;
    i = left;
    j = mid + 1;
    k = left;

    while (i <= mid && j <= right) {
        if (list[i] <= list[j])
            sorted[k++] = list[i++];
        else
            sorted[k++] = list[j++];
    }

    if (i > mid) {
        for (l = j; l <= right; l++)
            sorted[k++] = list[l];
    }
    else {
        for (l = i; l <= mid; l++)
            sorted[k++] = list[l];
    }

    for (l = left; l <= right; l++) {
        list[l] = sorted[l];
    }
}

void merge_sort(int list[], int left, int right) {
    int mid;

    if (left < right) {
        mid = (left + right) / 2;
        merge_sort(list, left, mid); 
        merge_sort(list, mid + 1, right);
        merge(list, left, mid, right);
    }
}

int main() {
	int arr[1000000];
	int n;
	scanf("%d", &n);

	for (int i = 0; i < n;i++) {
		scanf("%d", &arr[i]);
	}

    merge_sort(arr, 0, n - 1);

    for (int i = 0; i < n;i++) {
        printf("%d\n", arr[i]);
    }
	return 0;
}