삼성 코딩테스트 B형을 위한 퀵소트, 정렬 nlogn

 
#include <stdio.h>
 
void swap(int arr[], int a, int b){
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b]  = temp;
 }
 
void q_sort(int arr[], int s, int e){
    if(e-s<1) return;
    if(e-s==1) {
        if(arr[s]> arr[e]) swap(arr, s,e);
        return;
    }
    if(e-s==2){
        int p = s+1;
        if(arr[s] > arr[p]) swap(arr,s,p);
        if(arr[p]>arr[e]) swap(arr,p,e);
        if(arr[s] > arr[p] ) swap(arr,p,s);
        return;
    }
    
    int c = (e+s)/2;
    if(arr[c]> arr[s]) swap(arr,c,s);
    if(arr[s]>arr[e]) swap(arr,s,e);
    if(arr[c]>arr[s]) swap(arr,c,s);
    
    c = e;
    int p = s;
    
    while(p!=c ){
        if(p<c){
            if(arr[p]<arr[c]){
                c--;
            }
            else{
                swap(arr,p,c);
                int temp = p; p=c; c= temp; c++;
            }
        }
        else{
            if(arr[p]<arr[c]){
                swap(arr,p,c);
                int temp = p; p=c; c= temp; c--;
            }
            else{
                c++;
            }
        }
        
    }
    q_sort(arr,s,p-1);q_sort(arr,p+1,e);
}
 
int main() {
    int N = 0;
    scanf("%d", &N);
    int arr[100];
    for(int i =0; i<N;i++){
        scanf(" %d",&arr[i]);
    }
    q_sort(arr,0,N-1);
    for(int i =0; i<N;i++){
        printf("%d\n",arr[i]);
    }
 
    return 0;
}