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

분류: 정렬 /

 

문제

문제 링크

문제 설명

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

입력

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

출력

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

 

풀이

- Merge Sort 1

#include <iostream>
using namespace std;

void merge(int arr[], int start, int end) {
    int tmp[end-start];
    int mid = (start + end) / 2;
    int left = start, right = mid;
    for(int i = 0; i < end-start; i++) {
        if(right == end) tmp[i] = arr[left++];
        else if(left == mid) tmp[i] = arr[right++];
        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 - start];
}
void mergeSort(int arr[], int start, int end) {
    if(end - start <= 1) return;
    int mid = (start + end) / 2;
    mergeSort(arr, start, mid);
    mergeSort(arr, mid, end);
    merge(arr, start, end);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int N; cin >> N;
    int arr[N];
    for(int &x:arr) cin >> x;
    mergeSort(arr, 0, N);
    for(int x:arr) cout << x << '\n';
}

- Merge Sort 2

#include <iostream>
using namespace std;

int arr[1000001];
int tmp[1000001];

void mergeSort(int start, int end) {
    if(end - start <= 1) return;
    int mid = (start + end) / 2;
    mergeSort(start, mid);
    mergeSort(mid, end);
    for(int i=start, left=start, right=mid; i<end; i++) {
        if(right == end) tmp[i] = arr[left++];
        else if(left == mid) tmp[i] = arr[right++];
        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';
}

- Counting Sort

#include <iostream>
using namespace std;
const int MID = 1000000;

bool arr[2 * MID + 1];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    for(int i=0; i<n; i++) {
        int x; cin >> x;
        arr[MID + x] = true;
    }
    for(int i=0, cnt=0; cnt!=n && i<2*MID+1; i++) {
        if(arr[i]) {
            cnt++;
            cout << i - MID << '\n';
        }
    }
}