[알고리즘] CHAP 1. Divide and Conquer (분할정복) - Quicksort

지난 챕터에는 divide and conquer에 대해 다루어 보았다. 이번 챕터에서는 그 중에서도  퀵정렬에 대한 내용을 다루어 볼 예정이다. 목차는 다음과 같다.

• Quicksort?

divide and conquer에 대한 내용은 아래 링크에 작성하였다!

https://wanna-developer02.tistory.com/46

[알고리즘] CHAP 1. Divide and Conquer (분할정복) - mergesort

그럼 시작!

 

---

1. Quicksort?

퀵정렬은 하나의 리스트를 피벗값(pivot)을 기준으로 두 개의 비균등한 크기로 분할하고, 서브 배열을 재귀를 이용해 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하는 방법이다.

이를 divide and conquer의 순서로 정리하면 다음과 같다.

 

# Design strategy

- Divide

입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열로 분할한다. 보통 피벗값은 제일 앞에 있는 원소로 하며,  피벗값의 왼쪽엔 피벗보다 작은 원소들이, 오른쪽엔 큰 원소들이 있게 된다. 

- Conquer

STEP1을 서브배열에서도 반복하며 정렬한다. 

- Combine

정렬된 부분 배열들을 하나의 배열에 병합한다.

 

 

# Code

코드는 수도코드(Pseudo-Code)로 작성한다.

void quicksort(index low, index high) {
	index pivotpoint;
    if (high > low) {
    	partition(low, high, pivotpoint); // 피봇위치 설정
        quicksort(low, pivotpoint - 1); // 재귀
        quicksort(pivotpoint + 1, high);
    }
}

void partition(index low, index high, index& pivotpoint) {
	index i,j;
    keytype pivotitem;
    pivotitem = S[low];
    j = low;
    
    for (i = low + 1 ; i <= high ; i++) {
    	if (S[i] < pivotitem) {
        	j++;
            exchange S[i] and S[j];
        }
        pivotpoint = j;
        exchange S[low] and S[pivotpoint];
    }
}

 

Quicksort 과정

 

---

# Every-case Time Complexity

input size는 n = high - low + 1 이므로 누가 들어왔던 항상 n - 1번 비교해야 하기 때문에  비교 횟수는 항상 T(n) = n - 1이다.

 

# Worst-case Time Complexity

worst case는 이미 정렬이 되어있는 경우가 된다. 정렬이 되어있으면 일반적으로 맨 앞 원소를 pivot으로 두는 퀵정렬 특성상 pivot보다 작은 원소를 찾을 수 없어 subarray가 empty 상태가 된다. 

 

T(n) = T(0) + T(n - 1) + n - 1 이고, T(0) = 0이므로 T(n) = T(n - 1) + n - 1

따라서 W(n) = 1 + 2 + .. + (n - 1) = n(n - 1) / 2 ∈ θ (n^2)

 

# Average-case Time Complexity

pivot이 될 확률은 1/n이고, 정렬 횟수는 A(p - 1) + A(n - p)이므로 average time complexity는

A(n) = ∑ 1 / n [A(p - 1) + A(n - p)] + n - 1 = (2 / n) ∑ A(p - 1) + n - 1 

이를 풀어내면 A(n) ≒ θ(n lg n) 이 된다. (풀이과정이 복잡해 생략했다)

 

 

---

다음 게시물에서는 이번 챕터의 마지막 예시인 Master Theorem을 다뤄볼 예정이다!