[Algorithm] 백준 2751 수 정렬하기 2

기본적으로 O(N * logN)을 요구하는 문제는 최악의 경우 O(N^2)가 나올 수 있기 때문에, 아래처럼 퀵 정렬로 풀 경우 틀렸다고 처리됨.

 

그래서 일반적으로 C++알고리즘 STL 라이브러리를 사용함.

STL 라이브러리에서 제공하는 sort() 함수에서 별도의 처리를 거친 퀵 정렬은 최악의 경우에도 O(N*logN)을 보장함.

 

또는 병합 정렬이나 힙 정렬을 사용할 수도 있음,

#include <stdio.h>

int arr[1000000];
int n;



void Quick_Sort(int arr[], int start, int end){

    if(start >= end)
        return;
    
    
    int pivot = start;
    int i = start + 1;
    int j = end;
    
    
    while(i <= j){
    
        while(i <= end && arr[i] <= arr[pivot])
            i++;
            
            
        while(j > start && arr[j] >= arr[pivot])
            j--;
            
            
        if(i > j){
        
            int temp = arr[pivot];
            arr[pivot] = arr[j];
            arr[j] = temp;
        }
        else{
        
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    
    
    Quick_Sort(arr, start, j-1);
    Quick_Sort(arr, j+1, end);
}



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