퀵 정렬

partition을 통해 일부 진행 -> 그거를 가지고 부분 분할

즉, 대강 partition으로 기준을 정해놓고 큰지 작은지만 대략 분류하기

-> 작으면 오른쪽, 크면 왼쪽

-> 피봇은 어느쪽에도 포함x

 

1. partition(피봇 선정)

2. 퀵 정렬(Quick Sort)

 

알고리즘

 

QuickSort(A,left,right)
입력: 배열 A[left]~A[right]
출력: 정렬된 배열 A[left]~A[right]
if(left<right){
	//partitioning
	피봇을 A[left]~A[right]에서 선택하고,
    피봇을 A[left]와 자리를 바꾼 후,
    피봇과 배열의 각 원소를 비교하여
    피봇보다 작은 숫자들은 A[left]~A[p-1]로 옮기고,
    피봇보다 큰 숫자들은 A[p+1]~A[right]로 옯기며,
    피봇은 A[p]에 놓는다.
    QuickSort(A,left,p-1) // 피봇보다 작은 그룹
    QuickSort(A,p+1,right) //피봇보다 큰 그룹
}

 

void quick_sort(int list[], int left, int right)
{
	if(left<right){
    	int q=partition(list,left,right);
        quick_sort(list,left,q-1);
        quick_sort(list,q+1,right);
    }
}
int partition(int list[], int left, int right)
{
	int pivot, temp;
    int low, high;
    
    low=left;
    high=right+1;
    // 임의의 pivot 선택
    // pivot과 가장 왼쪽꺼 교환 -> pivot이 가장 왼쪽
    pivot=list[left];
    do{
    	do
        	low++;
        while(low<=right && list[low]<pivot); //low 이동
        do
        	high--;
        while(high>=left && list[high]>pivot); //high 이동
        if(low<high) SWAP(list[low], list[high], temp); //low와 high 교환
    }while(low<high); //(9,3,5,6,7,4,12,11)
    SWAP(list[left], list[high], temp); //pivot값과 high에 있는 값 교환 (4,3,5,6,7,9,12,11)
    return high;
}

 

예제

시간 복잡도

 

퀵 정렬의 성능은 피봇 선택이 좌우한다.

최악의 경우

 

: 피봇으로 항상 가장 작은 숫자가 선택되는 경우

- 피봇=1일 때: 8회(17,42,9,18,23,31,11,26)과 각각 1회 비교

- 피봇=9일 때: 7회(42,17,18,23,31,11,26)과 각각 1회 비교

- 피봇=11일 때: 6회(17,18,23,31,42,26)과 각각 1회 비교

...

- 피봇=31일 때: 1회(42)와 1회 비교

=> 총 비교 횟수: 8+7+6+...+1=36

 

시간 복잡도

(n-1)+(n-2)+(n-3)+...+2+1=n(n-1)/2=O(n^2)

 

최선의 경우

 

: 균등하게 분할되는 피봇 선택

O(n)*(층수) = O(n)*(logn) = O(nlogn)

* n/2^k=1 => k=logn

피봇 선정 방법

 

- 랜덤하게 선정

- 3 숫자의 중앙값으로 선정

- Median-of-Medians(Tukey's Ninther)

: 3등분한 후 각 부분에서 가장 왼쪽 숫자, 중간 숫자, 가장 오른쪽 숫자 중에서 중앙값을 찾은 후, 세 중앙값들 중에서 중앙값을 피봇으로 정한다.

 

성능 향상 방법

 

입력의 크기가 매우 클 때, 퀵 정렬의 성능을 더 향상시키기 위해, 삽입정렬을 동시에 사용

- 입력의 크기가 작을 때에는 퀵 정렬이 삽입 정렬보다 빠르지만은 않다.(∵ 순환함수 있기 때문)

==> 부분 문제의 크기가 작아지면 => 더 이상의 분할 중단하고 삽입 정렬 사용

 

퀵 정렬은 입력의 크기가 클 때 유용