[알고리즘]Quicksort

Quicksort

가장 첫번째 array의 값(pivot)을 기준으로 더 작은 값과 큰 값으로 나누어 정렬함

//Quicksort

void quicksort(index low, index high) {
	index pivotpoint;
    if(high > low) {
    	partition(low, high, pivotpoint); //pivotpoint를 기준으로 정렬
        quicksort(low, pivotpoint-1); // pivot보다 큰거
        quicksort(pivotpoint+1, high); //pivot보다 작은거
        
//partition

void parititon(index low, index high, index &pivotpoint) {
	index i, j;
    keytype pivotitem;
    pivotitem = S[low]; //가장 첫번째 값이 pivotitem
    j = low; //작은 값의 위치를 바꾸기 위한 변수
    for(i = low + 1; i <= high; i++) //전체 배열을 pivotitem과 비교
    	if(S[i] < pivotitem) { //해당 값이 pivotitem보다 작으면
        	j++;
            exchange S[i] and S[j];
        }
        pivotpoint = j; //pivotpoint를 넣어줌
        exchange S[low] and S[pivotpoint]; //pivotpoint에 povot값을 넣어줌

S[1] (pivot)을 기준으로 값을 확인한 후 마지막에 pivot을 pivotpoint에 넣어줌

 

-> 바뀐 값의 위치는 j에 들어있으니 최종적으로 pivotpoint는 j가 됨

 

 

 

---

Every Case Time Complexity (Partition)

Input size n = high - low + 1 //low + 1부터 high까지 검사함

∴T(n) = n - 1

---

Worst Case Time Complexity (Quicksort)

: 배열이 감소하지 않는 순서로 정렬된 경우가 최악의 경우일 것!. ex) 3 4 5 5 7 8 ...

-> array는 좌측의 빈 array와 우측의 하나의 array로 나뉘게 되는 상황을 반복하게 됨

- T(n) = T(0) + T(n - 1) + n - 1 //T(0)을 처리하고 T(n - 1)을 처리하고 partition을 처리해야함

T(0) = 0

∴ T(n) = T(n - 1) + n - 1

 

 

 

 

 

 

 

 

증명

- 귀납가설

- Induction Step

W(p - 1) // pivotpoint의 왼쪽

+ w(n - p) // pivotpoint의 오른쪽

+ n - 1 // Partition의 시간복잡도

-> 2차식이기 때문에 p = 1이거나 p = n 에서 최대값을 갖는다.

 

분자 값은 n(n-1)이고 분모 값은 2이기 때문에

∴ W(n) = n(n - 1)/2 ∈ Θ (n^2)

 

---

Average Case Time Complexity

 

- pivot위치가 p일 확률은 1/n

- pivot위치가 1/n일 때 정렬하는 평균 시간은 A(p - 1) + A(n - p)이고, Partition은 n - 1이다.

아무튼 계산 열심히 하면 A(n)은  ∈  Θ  (n lg n)이다.