[정렬 알고리즘] 02 퀵 정렬(Quick Sort)이론 및 구현

1. 퀵 정렬 개념

• 찰스 앤터니 리처드 호어(Charles Antony Richard Hoare)가 개발한 정렬 알고리즘
• 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속하며 불안정 정렬
• 평균적으로 매우 빠른 수행 속도를 자랑하지만 정렬을 위해 $O(\lg n)$만큼의 메모리를 필요
• 분할 정복 방법을 통해 정렬 수행
• 입력 자료들 중 하나의 요소(이를 피벗(pivot)이라 함)를 선택한 후 피벗을 기준으로 피벗보다 작은 요소와 큰 요소들을 나눔
• 나눠진 2개의 입력 자료들은 위와 같은 방식으로 분할되지 않을 때까지 반복

* 퀵 정렬은 다음과 같은 분할 정복을 통해 정렬을 수행함

① 분할(partition함수) : 배열 A[p, ..., r]을 두 부분 배열 A[p, ..., q-1]과 A[q+1, ..., r]로 분할
② 정복 : 퀵 정렬을 재귀호출해서 A[p, ..., q-1]과 A[q+1, ..., r]두 부분배열로 정렬
③ 결합 : 부분 배열이 이미 정렬되어있으므로 합치는 작업 필요하지 않음

---

2. 퀵 정렬 예제

---

3. 퀵 정렬 특성

1) 장점

• 속도가 매우 빠름(다른 $O(n \lg n)$의 시간 복잡도를 가진 정렬 알고리즘에 비해)
• 평균적인 경우에도 여전히 $O(n \lg n)$의 시간 복잡도를 가짐

2) 단점

• 정렬된 자료들에 대해서 불균형 분할에 의해 오히려 수행시간이 더 많이 걸림(즉, 기준 값(pivot)의 선택에 따라 틀려짐 -> 해결 : 중간 값을 기준으로 선택)
• 안정성이 없는 알고리즘

---

4. 퀵 정렬 분석

▶ Pseudo code(의사코드)

* partition함수는 $n=r-p+1$일 때, $\theta(n)$ => 분할과정에서 소요되는 시간 : $\theta(n)$
* 퀵 정렬의 수행시간은 분할 후 양쪽 배열의 크기가 비슷한지 그렇지 않은지에 따라 달라짐
* 분할의 균형도는 분할할 때 어떤 기준 원소를 사용하는지에 따라 달려있다

 

① Best Case(부분 문제 $n/2$)
ex)

$T(n) = 2T(n/2) + \theta(n)$

Recurrence식이 나왔으므로 재귀트리를 이용하여 시간 복잡도를 구함->(치환법을 통한 증명은 생략)

재귀 트리 확장

모든 레벨의 비용은 $cn$이며 깊이는 $\lg n$이므로 재귀 트리의 총 비용은 $n \lg n$

$\therefore O(n \lg n)$

 

② Worst Case($n-1$, 0으로 나누어진 경우)
ex)

$T(n) = T(n-1) + T(0) + \theta(n)$

          $= T(n-1) + \theta(n)$ // 크기 0인 배열에 대한 재귀호출은 즉시 리턴되므로 $T(0)=\theta(1)$

 

재귀 트리 확장

 

 

위 식에서 $n-k=1$일 때, $T(1)$까지 내려가므로 다시 식을 고치면

$\therefore O(n^2)$

 

※ 균등 분할
ex) 분할 알고리즘이 항상(똑같은 비율로) 9:1로 분할하는 경우

$T(n) \le T(9n/10) + T(n/10) +cn$

$\therefore O(n \lg n)$

"심지어 99:1로 분할하더라도 $O(n \lg n)$이 나옴"

하지만, 위와 같이 분할이 단계마다 똑같은 비율로 일어날 가능성은 거의 없다
즉, 평균적인 경우에 partition 결과 중에 "좋은 분할($n/2$)"과 "나쁜 분할($n-1, 0$)"이 섞여 있다.

ex)

좋은 분할과 나쁜 분할이 섞여있는 경우

위와 같이 나쁜 분할과 좋은 분할이 섞여있는 경우 크기가 각각 $0, (n-1)/2 - 1, (n-1)/2$이며,
비용은 $\theta(n) + \theta(n-1) = \theta(n)$이다.
나쁜 분할$\theta(n-1)$은 좋은 분할$\theta(n)$에 흡수되므로 결과적으로 좋은 분할

따라서, 좋은 분할과 나쁜 분할이 번갈아 가면서 발생할 때 퀵 정렬의 수행시간은 여전히 $O(n \lg n)$으로 좋은 분할만 나타내는 경우의 수행시간과 비슷

---

5. 퀵 정렬  시간 복잡도

1) Best Case(2개의 $n/2$의 부분 문제로 나눌 때)

① Recursion Tree의 깊이 : $\lg n$

② 각 level의 비용 : $n$

③ 시간 복잡도 : $O(n \lg n)$

 

2) Worst Case(n-1개와 0개짜리 부분 문제로 나눌 때)

① Recursion Tree의 깊이 : $n$

② 각 level의 비용 : $n$

③ 시간 복잡도 : $O(n^2)$

 

3) Average Case

- 부분 문제 크기가 각각 $\left\lfloor n/2 \right\rfloor$와 $\left\lceil n/2 \right\rceil - 1$이 되어 양쪽 모두 크기가 $n/2$이하인 경우

$T(n) = 2T(n/2) + \theta(n)$

① 시간 복잡도 : $O(n \lg n)$

 

4) 성능 및 평가

• 멀리 있는 값들끼리 교환이 일어나므로 불안정
• pivot 위치에 따라 성능 다르지만 최악의 경우와 같이 연속적으로 $n-1$개와 $0$개로 나눠질 확률 낮음
• 따라서, 평균적으로 $O(n \lg n)$의 성능을 보임

	Best	Avg	Worst
퀵 정렬	$O(n\lg n)$	$O(n\lg n)$	$O(n^2)$

---

6. 퀵 정렬 구현(C언어)

#include<stdio.h>

void quick_sort(int[], int, int);
int partition(int[], int, int);
#define SWAP(x, y, t) ((t)=(x), (x)=(y), (y)=(t))

int main()
{
	int length;
	int arr[10] = { 10, 28, 30, 2, 15, 8, 67, 45, 3, 11 };

	length = sizeof(arr) / sizeof(int);	

	quick_sort(arr, 0, length-1);
    
	return 0;
}

// quick_sort 함수
void quick_sort(int arr[], int left, int right) {
	
	int q;

	if (left < right) {	// 배열의 크기가 1일때 까지.
		q = partition(arr, left, right);	// pivot이 가리키는 배열의 index값 반환.
		quick_sort(arr, left, q - 1);		// 왼쪽 배열 정렬.
		quick_sort(arr, q + 1, right);		// 오른쪽 배열 정렬.
	}
}

// partition 함수
int partition(int arr[], int left, int right) {

	int low, high, pivot;
	int *temp;

	low = left;
	high = right + 1;
	pivot = arr[left];

	// 피벗을 기준으로 두 개의 배열로 나눔.
	do {
		do {
			low++;
		} while (low <= right && arr[low] < pivot);
		do {
			high--;
		} while (high >= left && arr[high] > pivot);
		if (low < high) {		// low가 high값보다 작을 때까지 양쪽 배열의 값을 SWAP해줌. 
			SWAP(arr[low], arr[high], temp);
		}
	} while (low < high);
	SWAP(arr[left], arr[high], temp);   // pivot이 가리키는 값과 pivot이 위치할 값 SWAP.

	return high;           // pivot 가리키는 index 반환.
}