Algorithm
22 May 2020

stl 보다 10배빠른 quick sort

quick sort

개요

  • 시간복잡도 : O(N*logN);

  • 시간복잡도는 merge sort와 같지만 일반적으로 quick sort가 더 빠르다고 한다. 하지만 quick sort의 pivot을 어떻게 잡느냐에 따라 또 다르다.


void quick(int* p,int left,int right){
    if(left>=right)return;
    int L=left;
    int R=right;
    int pivot=p[(L+R)/2];

    while(true){
        while(p[L]<pivot)L++;
        while(p[R]>pivot)R--;
        if(L>=R)break;
        int temp=p[L];
        p[L]=p[R];
        p[R]=temp;
    }

    quick(p,left,L-1);
    quick(p,r+1,right);
}
int main(){
    int arr[5] = { 5,2,3,1,4 };
    for(int i=0;i<5;i++){
        cout<<arr[i]<<'\n';
    }
}

결과값

1 2 3 4 5
Tags:
0 comments