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

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

 

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

 

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

---

정렬 문제.

처음에 퀵 정렬로 풀었으나 제출 전에 쎄한 느낌이 들어 구글링을 해봤더니 퀵정렬은 최악의 경우 시간복잡도가 O(n²)로, 시간초과의 위험이 있다고 하더라..

그리하여 병합 정렬을 구현하여 풀었다.

 

병합정렬 : 🔗

 

코드

#include <cstdio>

void merge(int* sorted, int* arr, int begin, int mid, int end);
void mergeSort(int* sorted, int* arr, int begin, int end);
void printArr(int* arr, int n);

int main(void) {
    int n;
    scanf("%d", &n);

    int* arr = new int[n];
    int* sorted = new int[n];

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

    delete[] arr;
    return 0;
}

void merge(int* sorted, int* arr, int begin, int mid, int end) {
    int i, j, k;
    i = begin;
    j = mid + 1;
    k = begin;

    while(i <= mid && j <= end) {
        if(arr[i] <= arr[j]) {
            sorted[k] = arr[i];
            i++;
        }
        else {
            sorted[k] = arr[j];
            j++;
        }
        k++;
    }
    if(i > mid) {
        for(int a = j; a <= end; a++, k++)
            sorted[k] = arr[a];
    }
    else {
        for(int a = i; a <= mid; a++, k++)
            sorted[k] = arr[a];
    }

    for(int a = begin; a <= end; a++)
        arr[a] = sorted[a];
}

void mergeSort(int* sorted, int* arr, int begin, int end) {
    int mid;
    if(begin < end) {
        mid = (begin + end) / 2;
        mergeSort(sorted, arr, begin, mid);
        mergeSort(sorted, arr, mid + 1, end);
        merge(sorted, arr, begin, mid, end);
    }
}

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