정렬 (7) - 개선된 퀵 정렬 (Improved Quick Sort)

1. 난수 분할

Pivot이 항상 편향되는 최악의 경우를 막기 위해 Pivot값을 매번 Random한 위치에서 잡는 방법.

void quick_sort_random(int arr, int l, int r){
	
    int pivot = random();
    swap(arr[pivot], arr[r-1]);
    // random한 pivot 선정
    
    if(l < r){
    	int p = partition(arr, l, r);
        
        quick_sort_random(arr, l, p-1);
        quick_sort_random(arr, p, r);
    }
}

 

2. Median of Three 

배열의 가장 첫 인덱스, 끝 인덱스, 중간 인덱스에 해당하는 값들을 정렬하고, 중간 값을 Pivot으로 사용하여 Quick Sort를 수행하는 방법,

void quick_sort_median_of_three(int *arr, int l, int r){
	
    sort_three(arr[0], arr[(r-1)/2], arr[r-1]);
    int pivot = arr[(r-1)/2];
    // 0번, n/2번, n번째 원소를 정렬하고 
    // 중간 크기를 가지는 원소를 pivot으로 선정
    
    if(l < r){
        int p = partition(arr, l, r);
        
        quick_sort_median_of_three(arr, l, p-1);
        quick_sort_median_of_three(arr, p, r);
    }
}

 

3. 삽입정렬과 함께 사용

만약 arr의 size가 특정 수 (e.g. 200) 이하라면 삽입정렬, 그 것보다 크면 퀵정렬을 사용하여 정렬하는 것이 성능이 더욱 좋음. 가장 빠른 조합은 Median of Three와 삽입 정렬을 함께 사용하는 것임.

void quick_insertion_sort(int *arr, int l, int r){

	int size = sizeof(arr)/sizeof(arr[0]);
    
	if(size > 200){
    	int p = partition(arr, l, r);
        
        quick_insertion_sort(arr, l, p-1);
        quick_insertion_sort(arr, p, r);
        
    }else{
    	insertion_sort(arr, size);
    }
}