[백준] 2751번 : 수 정렬하기2

[수 정렬하기]

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

문제

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

입력

수의 개수 N ( 1 <= N <= 1,000,000 )이 주어진다.

그 다음 줄 부터 N개의 줄에 걸쳐 숫자가 주어진다. 

( 절대값은 1,000,000보다 작거나 같은 정수이며, 수는 중복되지 않는다. )

출력

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

제한조건

시간 : 1초

메모리 : 128MB

Solution

수를 정렬하는 다양한 방법이 존재한다.

그러나, 가장 쉽다고 여겨지는 선택정렬이나 버블정렬의 경우 O(N^2)이기 때문에 시간 안에 풀 수 없다.

때문에 여기서는 이 문제를 퀵소트를 이용하여 해결한다. 

Source Code

#include<stdio.h>
#define MAX 1000000    // 데이터 개수의 MAX 범위
#define qSWAP(x, y) { int t = x; x = y; y = t; }  // 간단한 SWAP 함수
int N, arr[MAX]; // 데이터 개수와 저장할 배열
 
void qSort(int *array, int left, int right) {
    int mLeft = left, mRight = right;
    int pivot = array[(left + right) / 2];
    
    while(mLeft <= mRight) {
        while(pivot > array[mLeft]) mLeft++;
        while(pivot < array[mRight]) mRight--;
        
        if(mLeft <= mRight) {
            qSWAP(array[mLeft], array[mRight]);
            mLeft++, mRight--;
        }
    }
 
    if(left < mRight) qSort(arr, left, mRight);
    if(mLeft < right) qSort(arr, mLeft, right);
}
 
int main() {
    int idx;
    
    // 입력    
    scanf("%d", &N);
    for(idx = 0; idx < N; idx++) {
        scanf("%d", &arr[idx]);
    }
    
    qSort(arr, 0, N - 1);    // 배열 인덱스 0 ~ N-1 까지 퀵소트
    
 
    // 출력
    for(idx = 0; idx < N; idx++) {
        printf("%d ", arr[idx]);
    }
 
    return 0; 
}

실행화면