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

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

2751번: 수 정렬하기 2

문제

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

입력

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

출력

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

예제 입력 1

5

5

4

3

2

1

예제 출력 1

1

2

3

4

5

 

처음에는 삽입정렬로 해보았는데 시간초과가 떴다.

그래서 퀵정렬로도 시도했지만 시간초과가 떴다.

그래서 머지정렬을 이용했더니 성공했다.

이를 통해 머지 정렬을 이용하는 것이 가장 빠르다는 것을 알 수 있었다.

 

#include <stdio.h>
#include <stdlib.h>
#define SWAP(x,y,tmp)((tmp)=(x),(x)=(y),(y)=(tmp))
#define MAX_SIZE 1000000
 
/*퀵정렬도 안됨
int c = 0;
int partition ( int list[], int left, int right, int n ) 
{
    int tmp;
    int low = left+1;      // left는 pivot
    int high = right;
    int pivot = list[left];     // 피벗 설정 
 
    while(low <= high ){        // low와 high가 역전되지 않는 한 반복 
        for ( ; low <=right && list[low] < pivot ; low++) ; //low증가
        for ( ; high>=left && list[high]> pivot ; high--) ; //high감소
        if( low < high )        // 선택된 두 레코드 교환 
            SWAP(list[low],list[high],tmp);
    } 
    SWAP(list[left],list[high],tmp); // high와 피벗 항목 교환 
    c++;
    return high;
}
 
// 퀵 정렬 : 배열의 left ~ right 항목들을 오름차순으로 정렬하는 함수
void quick_sort ( int list[], int left, int right, int n ) 
{ 
    int q;
    if( left<right ){ // low,high증가시키며swap, 마지막 pivot 교환
    q = partition(list,left,right, n); 
    quick_sort (list, left, q-1, n);    // q는 처리한 pivot
    quick_sort (list, q+1, right, n);
    }
}
*/
 
static void merge(int list[], int left, int mid, int right) { 
    int i, j, k = left, l;
    static int sorted[MAX_SIZE];
 
    for( i=left, j=mid+1 ; i<=mid && j<=right ; ) 
        sorted[k++] = (list[i]<=list[j]) ? list[i++] : list[j++];
    if( i > mid )
        for( l=j ; l<=right ; l++, k++ )
            sorted[k] = list[l];
    else
        for( l=i ; l<=mid ; l++, k++ )
            sorted[k] = list[l];
    for( l=left ; l<=right ; l++ ) 
        list[l] = sorted[l];
}   
 
void merge_sort ( int list[], int left, int right ) { 
    if( left<right ) {
        int mid = (left+right)/2;    
        merge_sort(list, left, mid);
        merge_sort(list, mid+1, right);
        merge(list, left, mid, right);
    }
}
 
int main(){
    int n;
    int list[MAX_SIZE];
 
    scanf("%d", &n);
 
    for(int i=0; i<n; i++)
        scanf("%d",&list[i]);
    merge_sort(list,0,n-1);
 
    /*삽입정렬은 시간초과 뜸
    int least,tmp,j;
    for(int i=0; i<n-1; i++){
        least=i;
        for(j=i+1; j<n; j++)
            if(list[j]<list[least])
                least=j;
        if(least!=i)
            swap(list[least],list[i],tmp);
    }
    */
 
    for(int i=0; i<n; i++)
        printf("%d\n", list[i]);
 
}