[BAEKJOON ONLINE JUDGE] 2750번 : 수 정렬하기

시간 제한 : 1 초

 

메모리 제한 : 128 MB

 

문제

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

 

입력

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

 

출력

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

---

#include<stdio.h>

void swap(int* arr, int a, int b);
int sort(int* arr, int l, int r);
void qsort(int* arr, int l, int r);

int arr[1000];

int main()
{
    int n  =0;
    scanf(" %d", &n);
    
    for (int i = 0; i < n; i++)
        scanf(" %d", &arr[i]);
    
    qsort(arr, 0, n-1);
    
    for(int i = 0; i < n; i++)
        printf("%d\n", arr[i]);
    
    return 0;
}

void swap(int* arr, int a, int b)
{
    int tmp = arr[a];
    arr[a] = arr[b];
    arr[b] = tmp;
}

int sort(int* arr, int l, int r)
{
    int p = l;
    int lv = l + 1;
    int rv = r;

    while (lv <= rv) {
        while ((arr[lv] <= arr[p]) && (lv <= r))
            lv++;
        while ((arr[p] <= arr[rv]) && (l+1 <= rv))
            rv--;
        if (lv <= rv)
            swap(arr, lv, rv);
    }
    swap(arr, p, rv);

    return rv;
}

void qsort(int* arr, int l, int r)
{
    if (l <= r) {
        int p = sort(arr, l, r);
        qsort(arr, l, p - 1);
        qsort(arr, p + 1, r);
    }
}