Quick Sort

Quick Sort

int partition(int *arr, int left, int right){
    int i = left;
    int j = right;
    int mid = (i + j) / 2;
 
    int tmp = arr[mid];
    arr[mid] = arr[i];
    arr[i] = tmp;
 
    int pivot = arr[i];
 
    while(i < j){
        while(pivot < arr[j]){
            --j;
        }
 
        while(i < j && pivot >= arr[i]){
            ++i;
        }
 
        tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
 
    arr[left] = arr[i];
    arr[i] = pivot;
 
    return i;
}
 
void quickSort(int arr[], int left, int right){
    if(left < right){
        int pivot = partition(arr, left, right);
 
        quickSort(arr, left, pivot-1);
        quickSort(arr, pivot+1, right);
    }
}

• 퀵정렬은 분할-정복 방식의 O(n logn)의 속도를 지닌 빠른 정렬기법이며,
  같은 시간 복잡도를 지닌 정렬기법이라도 일반적인 경우에는 퀵정렬이 제일 빠른다.
• 그 이유는 캐시메모리의 히트율이 높은 in-place 기법이며,
  매 라운드마다 pivot의 위치가 정해져서 1개의 원소가 정렬 대상에서 빠져나가기 때문인다. 
• 정렬된 상태의 배열을 만날 때 최악의 경우로 O(n^2) 속도를 지니지만, 최선, 평균 시간 복잡도는 O(n logn) 이다.
• 이러한 경우를 극복하기 위해 pivot 선정을 랜덤, 중간값으로 하는 다양한 방식들이 있다.
• partition 함수는 pivot을 기준으로 그 수보다 작은 수들의 배열, pivot, 큰 수들의 배열로 정렬하는 역할로 O(n) 을 차지한다.
• quickSort 함수는 partition을 통해 구한 pivot의 위치를 기준으로 또다시 partition을 호출하는 분할하는 역할로 O(logn)을 차지한다.
• in-place 정렬이므로 공간복잡도는 O(n) 이다,
• 퀵정렬은 unstable sort 이다.