chap3-2 Quick Sort

Quick sort

Divide : pivot element를 선택하고, pivot을 기준으로 subarray를 나누기 때문에 시간복잡도는 O(n)이다.

Conquer : subarray를 recursive하게 정렬해준다. tree의 깊이에 비례하므로 시간복잡도는 O(logn)이고 subarray의 크기를 m1과 m2라고 했을 때, conquer의 비용은 T(m1)+T(m2)가 된다.

combine : 할 필요가 없다.(O(1) or 0)

void quick_sort(int *n, int left, int right){
    int pivot;
    
    if(right-left>0){
        //divide
        pivot=partition(n,left,right);
        
        //conquer
        quick_sort(n,left,pivot-1);
        quick_sort(n,pivot+1,right);
    }
}

int partition(int* n,int left,int right){
    int i,pivot;
    //printf("Array : ");
    //for(int i=left;i<=right;i++) printf("%d ",n[i]);
    putchar('\n');
    pivot = left;
    for(i=left;i<right;i++){
        if(n[i]<n[right]){
            //printf("change %d %d\n",n[i],n[pivot]);
            SWAP(n[i],n[pivot]);
            pivot++;
        }
    }
    //printf("change %d %d\n",n[right],n[pivot]);
    SWAP(n[right],n[pivot]);
    return pivot;
}

 

quick sort 결과

---

정해지는 pivot이 계속 재수없게 array의 최솟값이나 최댓값이 된다면 skewed한 depth가 n인 tree가 만들어져 시간복잡도는 O(n^2)이 될 것이다. 하지만 일반적으로 depth가 logn인 tree가 만들어지기 때문에 평균적인 시간복잡도는 O(nlogn)이다.

---

Average Case Time Complexity