백준 2751 수 정렬하기 2 / C++

문제 : 2751

풀이 point

입력 받은 수를 정렬하면 되는 아주 간단한 문제이다.

라이브러리 정렬 함수는 보통 퀵정렬을 사용한다.
퀵 정렬은 평균 O(NlogN)이며, 최악의 경우 O(N^2)이다.
하지만 라이브러리는 최악의 경우에 도달하지 않도록 최대한의 장치를 해두었기 때문에
걱정하지 않고 써도 된다.

풀이 방법

라이브러리 함수를 쓰면 된다.
직접 만들고 싶다면 mergeSort가 있다.
quickSort는 직접 만들시 최악의 경우에 도달할 수 있기 때문에 좋지 않다.

코드

• 라이브러리 정렬 함수

int N;
    std::cin >> N;

    for(int i{0}; i<N; ++i) std::cin >> arr[i];

    std::sort(arr, arr+N);

    for(int i{0}; i<N; ++i) std::cout << arr[i] << '\n';

• mergeSort

#include <iostream>

int arr[1'000'001];
int tmp[1'000'001];

void merge(int st, int en){
    int mid = (st+en) / 2;
    int ridx{mid}; int lidx{st}; 
    for(int i{st}; i<en; ++i){
        if(lidx == mid) tmp[i] = arr[ridx++];
        else if(ridx == en) tmp[i] = arr[lidx++];
        else if(arr[lidx] > arr[ridx]) tmp[i] = arr[ridx++];
        else tmp[i] = arr[lidx++];
    }
    for(int i{st}; i<en; ++i) arr[i] = tmp[i];
}

void mergeSort(int st, int en){
    if(st+1 == en) return;
    int mid = (st+en) / 2;
    mergeSort(st, mid); //mergeSort에 mid는 포함안됨
    mergeSort(mid, en); //end 포함 안됨
    merge(st, en);
}

int main(){

    int N;
    std::cin >> N;
    for(int i{0}; i<N; ++i){
        std::cin >> arr[i];
    }
    mergeSort(0, N);

    for(int i{0}; i<N; ++i){
        std::cout << arr[i] << '\n';
    }
    
    return 0;
}