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

---

0. 문제

 

https://www.acmicpc.net/problem/2751

 

1. 아이디어

 

1) 위는 합병정렬(Merge Sort), 아래는 퀵정렬(Quick Sort)로 구현했다.

(퀵소트는 백준에서 시간초과가 뜬다.. pivot값을 잘 설정해주면 될 듯하다)

 

2. 소스코드

 

#include <iostream>
#include <utility>
int arr[1000000];
int tmp[1000000];
void merge(int st, int ed) // Merge Sort!
{
    int mid = (st + ed) / 2;
    int idx = st;
    int idx1 = st;
    int idx2 = mid;
 
    while (idx1 < mid && idx2 < ed)
    {
        if (arr[idx1] < arr[idx2])
            tmp[idx++] = arr[idx1++];
        else
            tmp[idx++] = arr[idx2++];
    }
    while (idx1 < mid)
        tmp[idx++] = arr[idx1++];
    while (idx2 < ed)
        tmp[idx++] = arr[idx2++];
    for (int i = st; i < ed; i++) arr[i] = tmp[i];
}
void merge_sort(int st, int ed)
{
    if (ed - st == 1) return;
    if (ed - st == 2)
    {
        if (arr[st] > arr[st+1])
            std::swap(arr[st], arr[st+1]);
        return;
    }
    int mid = (st + ed) / 2;
    merge_sort(st, mid); 
    merge_sort(mid, ed);
    merge(st, ed);
}
 
int main()
{
    int N;
    std::cin >> N;
 
    for (int i = 0; i < N; i++)
        std::cin >> arr[i];
    merge_sort(0, N);
 
    for (int i = 0; i < N; i++)
        std::cout << arr[i] << '\n';
}

#include <iostream>
#include <utility>
int arr[1000000];
void quick_sort(int* arr, int st, int ed) // Quick Sort!
{ 
    if (ed - st <= 1) return;
 
    int pivot = arr[st];
    int l = st + 1;
    int r = ed - 1;
 
    while (1)
    {
        while (l <= r && arr[l] <= pivot) l++;
        while (l <= r && arr[r] >= pivot) r--;
 
        if (l > r) break;
 
        std::swap(arr[l], arr[r]);
    }
    std::swap(arr[st], arr[r]);
    quick_sort(arr, st, r);
    quick_sort(arr, r+1, ed);
}
int main()
{
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    int N;
    std::cin >> N;
    for (int i = 0; i < N; i++)
        std::cin >> arr[i];
 
    quick_sort(arr, 0, N);
    for (int i = 0; i < N; i++)
        std::cout << arr[i] << '\n';
}

 

3. 결과

 

 

4. 피드백

 

• bubble sort, merge sort, quick sort, counting sort, radix sort 등을 잘 이해하자!!!

• 퀵소트는 운 좋으면 NlogN의 시간복잡도를 가지지만 최악의 경우  N^2의 시간복잡도를 가지니 주의하자..

---