2751-수 정렬하기2

www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

본 문제는 정렬에 관한 문제입니다. 무분별한 C++ STL 사용으로 몇몇 정렬 알고리즘의 구현 방법을 잊은터라 정렬 알고리즘을 복습할겸 알고리즘 문제도 풀겸 일석이조의 효과를 누리고자 해당 문제를 풀었습니다.

 

코드를 제출하기전에 직감적으로 $O(N^2)$의 복잡도를 갖는 정렬 알고리즘(Selection Sort, Insertion Sort, Bubble Sort)으로는 문제를 통과할 수 없음을 느꼈습니다.

 

 $O(NlogN)$의 복잡도를 갖는 정렬 알고리즘이 필요해보입니다. 서치해보니 Merge Sort, Quick Sort, Heap Sort가 눈에 들어왔습니다. 이 중, 대표적인 정렬 알고리즘인 Quick Sort를 사용하여 문제를 풀이하고자 합니다. 2~3 번 정도 직접 구현까지 했었던 알고리즘인데 기억이 잘 나지 않았습니다. 이번엔 머리 속에 확실히 각인 시키고자 합니다.

 

Quick Sort는 Divide, Conquer 단계로 구성되며 Recursive 하게 동작되는 In-place 알고리즘입니다.

 

1. Divide 단계에서는 Array A[p..r]를 Pivot A[q]를 기준으로 두 개의 Subarray A[p..q-1], A[q+1..r]로 분할합니다. 이때, A[p..q-1] $\le$A[q] 이고 A[q+1..r] $\ge$A[q]를 만족해야합니다.

 

2. Conquer 단계에서는 나누어진 두 개의 Subarray A[p..q-1], A[q+1..r]를 정렬합니다. (by recursive calls to quicksort)

 

Divide 단계에서 선택되는 Pivot이 Array의 Median(중앙값)이라면 복잡도는 $O(NlogN)$, 최솟값이라면 복잡도는 $O(N^2)$입니다. 즉, 정렬전에 Array의 원소 값이 어떻게 배치되어 있는지와 Pivot을 선택하는 방법에 따라 복잡도가 변하게 됩니다.

 

그렇게 제가 구현한 Quick Sort는 시간초과가 발생하였습니다. 아무래도 Worst Case 복잡도가 $O(N^2)$이므로 보니 해당 케이스에서 시간초과가 발생한듯 합니다.

 

데이터에 상관없이 항상 $O(NlogN)$의 복잡도를 갖는 Merge Sort를 구현해보았습니다. Merge Sort는 정리가 잘된 글이 많다보니 설명을 따로 작성하지는 않겠습니다. Merge Sort의 경우 모든 테스트 케이스를 통과할 수 있었습니다. 

 

Merge Sort의 경우 구현에 따라 차이가 있겠지만 대개 $O(N)$의 추가적인 공간 복잡도를 요구하고 구현에 따라 다수번의 메모리 할당이 실행될 수 있습니다. 저는 Merge Sort를 구현함에 있어 메모리의 할당을 최대한 줄이도록 동작 과정에서 메모리 할당이 딱 한 번만 실행되게끔 코드를 구현하였습니다. 아래 코드의 void merge() 함수 내에서 메모리 할당이 매번 일어나도록 구현했을때와 비교하였을때 생각보다 시간 차이는 크게 존재하지 않았습니다. 각각에 소요되는 수행시간은 784ms, 724ms만큼 걸렸으며 메모리 할당 횟수를 1회로 줄였을 때, 약 60ms의 시간을 절약할 수 있었습니다.

코드

#include <iostream>
using namespace std;

void merge(int* array, int* sorted_array, int l, int middle, int r)
{
    int len = r - l + 1;

    int i = l;
    int j = middle + 1;

    int k = 0;//정렬되는 원소들의 위치를 가르킴
    
    while(i <= middle && j <= r)
    {
        sorted_array[k++] = (array[i] <= array[j])? array[i++]:array[j++];
    }
	
    //아래 두 while 문 중 실제로 한 조건에만 걸림 무.조.건
    while(j <= r)
    {
        sorted_array[k++] = array[j++];
    }
	
    while(i <= middle)
    {
        sorted_array[k++] = array[i++];
    }

    for(int i = 0; i < len; i++) 
    {
        array[l + i] = sorted_array[i];
    }
}

void partition(int* array, int *sorted_array, int l, int r)
{
    if(l < r)
    {
        int middle = (l + r) / 2;
        partition(array, sorted_array, l, middle);
        partition(array, sorted_array, middle + 1, r);
        merge(array, sorted_array, l, middle, r);
    }
}
void merge_sort(int* array, int l, int r)
{
    int len = r-l+1;
    
    if(len == 1) return;

    int *sorted_array = new int[r-l+1];
    partition(array, sorted_array, l, r);

    delete[] sorted_array;
}

int main()
{
    //freopen("2751.txt", "r", stdin);
    int N;
    int* array;

    cin >> N;
    array = new int[N];
    for(int i = 0; i < N; i++) cin >> array[i];

    merge_sort(array, 0, N-1);

    for(int i = 0; i < N; i++) cout << array[i] << '\n';
    delete[] array;
    return 0;
}