[백준 - 11931] 수 정렬하기 4 - C++

분류: 정렬 /

 

문제

문제 링크

문제 설명

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

입력

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

출력

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

 

풀이

#include <iostream>
using namespace std;

int arr[1000001], tmp[1000001];

void mergeSort(int start, int end) {
    if(end - start <= 1) return;
    int mid = (start + end) / 2;
    mergeSort(start, mid);
    mergeSort(mid, end);
    int left = start, right = mid;
    for(int i=start; i<end; i++) {
        if(left == mid) tmp[i] = arr[right++];
        else if(right == end) tmp[i] = arr[left++];
        else if(arr[left] >= arr[right]) tmp[i] = arr[left++];
        else tmp[i] = arr[right++];
    }
    for(int i=start; i<end; i++) arr[i] = tmp[i];
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int N; cin >> N;
    for(int i=0; i<N; i++) cin >> arr[i];
    mergeSort(0, N);
    for(int i=0; i<N; i++) cout << arr[i] << '\n';
}

 

`내림차순`