[알고리즘 / 분할정복] #2 퀵 정렬 (Quick Sort)

퀵 정렬 (Quick Sort)

💡 피봇(Pivot)을 기준으로 왼쪽에 작은 수, 오른쪽에 큰수를 놓는 정복 후 분할하는 알고리즘이다.

 

퀵 정렬은 정확하게는 정복 후 분할을 하는 알고리즘이다.

퀵 정렬은 문제를 2개의 크기가 일정하지 않은 부분문제로 분할한다. 그리고 하나의 중점이 되는 원소(Pivot)를 두고 중점 기준 왼편에는 더 작은수, 오른편에는 더 큰 수를 위치하도록 분할한다.

피봇은 어느 쪽에서든 부분에 포함되지 않아야한다.

 

---

시간복잡도

퀵정렬의 성능은 피봇 선택에 좌우된다.

피봇이 가장 작은 수 or 가장 큰 수로 선택되면 한 부분이 치우치는 분할을 야기한다.

 

 

---

최악의 경우

퀵 정렬의 최악의 예제로 항상 가장 작은/큰 숫자를 선택하게 된다면 발생하는 시간복잡도에 대해 알아보자.

1. 피봇 1 : 남아있는 각 원소들과 총 8회 비교
2. 피봇 9 : 남아있는 각 원소들과 총 7회 비교
3. 피봇 11 : 남아있는 각 원소들과 총 6회 비교
4. 피봇 17 : 남아있는 각 원소들과 총 5회 비교
5. 피봇 18 : 남아있는 각 원소들과 총 4회 비교
6. 피봇 23 : 남아있는 각 원소들과 총 3회 비교
7. 피봇 26 : 남아있는 각 원소들과 총 2회 비교
8. 피봇 31 : 남아있는 각 원소들과 총 1회 비교

 

따라서 총 비교 횟수는 (n - 1)!이다.

즉, 크기가 n인 최악의 퀵 정렬 경우의 시간복잡도는 다음 공식이 성립된다.

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

 

 

---

최선의 경우

 

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=sehoon95&logNo=80212692808

 

항상 부분문제가 절반으로 분할된다면 각 층에서는 크기가 n인 배열의 각 원소가 각 부분의 피봇과 1회씩 비교된다면 비교 횟수는 O(n)이다.

층수는 log_2n으로 정의되는데 이는 크기가 n인 배열일 때 층수(k) = log_2n이기 때문이다.

그러므로 퀵 정렬의 최선의 경우 시간복잡도는 다음이 성립된다.

 

 

---

평균적 경우

퀵 정렬의 평균 경우는 최선의 경우와 동일하게 O(nlog_2n)이다.

공간복잡도

퀵 정렬의 공간복잡도는 크기가 n인 배열 안에서 원소를 이동시키며 정렬이 수행되므로 O(n)이다.

퀵 정렬 피봇 선정 방법

퀵 정렬의 불균형한 분할을 완화하기 위해 사용되는 대표적인 방법들이다.

1. 랜덤하게 선정
2. "가장 왼쪽 수, 중간 수, 가장 오른쪽 수"이 3개의 숫자 중에서 중앙 값을 피봇으로 선정
   ex) 26(왼쪽), 1(중간), 36(오른쪽) = 26(왼쪽) 선정

입력의 크기가 매우 클 경우, 삽입 정렬을 동시에 사용하기도 한다.

입력 크기가 작다고 퀵 정렬이 삽입 정렬보다 빠르지는 않다. 이는 퀵 정렬은 재귀 호출로 수행되기 떄문이다. 즉 부분문제의 크기가 작아지면, 더이상의 분할을 중단하고 삽입을 사용하는 것이다.

 

---

알고리즘 장단점

장점

퀵 정렬은 추가적인 메모리의 공간을 필요로하지 않는다. 이는 커다란 크기의 입력에 대해 가장 좋은 성능을 보이는 정렬 알고리즘이 되도록 하였다.

또한 피봇의 선정 기준에 따라 실질적으로 어느 정렬 알고리즘보다 좋은 성능을 보인다.

 

단점

피봇에 따라 시간복잡도가 크게 달라진다. 즉 안정성이 보장되지 않는다.

이는 피봇을을 이상적인 값으로 선택했다면 nlogn, 최악의 기준값을 선택할 경우 n^2라는 시간복잡도를 갖게 된다.

 

---

코드 예제

💡 수도코드

QuickSort(A, left, right)
입력 : 배열 A[left]~A[right]
출력 : 정렬된 배열 A[left]~A[right]

if(left < right)
{
	1. 피봇을 A[left]~A[right] 중에 선택
	2. 피봇을 A[left]와 자리 변경
	3-1. 피봇과 각 배열의 원소를 비교, 피봇보다 작은 수는 피봇의 왼편(A[left]~A[pivot-1])으로 옮긴다.
	3-2. 피봇보다 큰 수는 피봇의 오른편(A[pivot+1]~A[right])으로 옮긴다.
			*피봇은 항상 A[pivot]에 위치해야한다.
	
	QuickSort(A, left, pivot-1)    // 피봇보다 작은 그룹 재귀 함수 호출
	QuickSort(A, pivot + 1, right) // 피봇보다 큰 그룹 재귀 함수 호출
}

의사코드를 통해 다음을 확인할 수 있다.

1. 가장 왼쪽 원소 인덱스가 가장 오른쪽 원소 인덱스보다 작은지 크기를 확인한다.
   1. 왼쪽이 더 작으면 분할할 수 있는 충분한 크기이다.
   2. 왼쪽이 더 작지 않으면 분할할 수 없는 크기이다.
2. 1번 순서에서 피봇을 선정한다. (선정 기준은 상황에 맞추어 하는 것이 좋다.)
3. 2번 순서에서 피봇을 배열의 첫자리로 옮긴다.
4. 3번 순서에서 피벗보다 작은 수와 큰 수를 서로 다른 방향에 나누어 넣는다.
5. 마지막으로 남은 피봇의 정보를 재귀 함수로 다시 넘긴다.

 

💡 C++ 코드

/// 정렬되어야하는 배열의 첫 값, 중앙 값, 끝 값 중에서 중간 값 구하는 함수
/// <data1 : int *left>   가장 왼쪽 배열 원소
/// <data2 : int *middle> 중앙 배열 원소
/// <data3 : int *right>  가장 오른쪽 배열 원소
/// <return : int> 주어진 세개의 원소 중에서 중간 값을 반환
int* 퀵정렬::middle(int *left, int *middle, int *right)
{
	// 중앙 원소가 중간 값이면 반환
	if ((*left >= *middle && *middle >= *right) || (*right >= *middle && *middle >= *left))
		return middle;
	
	// 왼쪽 원소가 중간 값이면 반환
	if ((*middle >= *left && *left >= *right) || (*right >= *left && *left >= *middle))
		return left;
	
	// 오른쪽 원소가 중간 값이면 반환
	if ((*left >= *right && *right >= *middle) || (*middle >= *right && *right >= *left))
		return right;
	
	// 예외 처리
	return left;
}

/// 두 정수를 바꾸는 함수
/// <data1 : int *a> b와 바뀔 수
/// <data2 : int *b> a와 바뀔 수
void 퀵정렬::swap(int *a, int *b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}

/// 퀵 정렬 함수
/// <data1 : int A[]>   정렬해야하는 배열
/// <data2 : int begin> 배열의 시작점
/// <data3 : int end>   배열의 끝점
void 퀵정렬::QuickSort(int A[], int begin, int end) {
	// 시작점이 끝점보다 크거나 같으면 더이상 비교할 배열이 없는 것으로 함수를 나간다.
	if (begin >= end) return;

	////////////////////////////////
	//피봇 정의 시작
	//중간 값을 가지는 pivot을 구하는 함수
	int *pivot = 퀵정렬::middle(&A[begin], &A[(end/2)], &A[end]); // 처음, 중간, 끝의 배열을 비교하여 피봇 생성

	// 피봇이 첫 배열이 아니라면 첫 배열로 이동시키며 첫 배열 값을 피봇과 교환한다.
	if (pivot != &A[begin]) {
		퀵정렬::swap(&A[begin], pivot); // 첫 배열과 피봇의 값을 교환
	}

	pivot = &A[begin]; // 피봇을 맨 왼편 배열로 선언

	/////////////////////////////////
	int b = begin;
	int e = end;

	// 앞에서부터 큰 수를 찾는 b와 뒤에서부터 작은 수를 찾는 e가 서로 같은 위치가 아니라면 반복
	while (true) {
		// 피봇보다 큰 값을 찾는 반복자
		// b의 원소가 피봇보다 작고 b가 e보다 작을때 계속 다음 원소를 찾는다.
		while (A[b] <= *pivot && b < e) 
		{
			b++; // 큰 값이 아니면 다음 값을 봄
		}
		// 피봇보다 작은 값을 찾는 반복자
		// e의 원소가 피봇보다 크고 b가 e보다 작을때 계속 다음 원소를 찾는다.
		while (A[e] > *pivot && b < e) 
		{
			e--; // 작거나 같은 값이 아니면 다음 값을 봄
		}
		
		// b와 e가 같으면 원소 위치를 바꾸거나 탐사를 할 이유가 없기에 반복문을 나간다.
		if(b == e) break;

		// 위 두 조건을 만족하면 왼편에서 더 큰수가 오른편에서 더 작은 수가 발견된 것으로 둘을 바꾸어야한다.
		// 위의 두 반복문이 완료되면 e와 b는 같은 자리의 수를 가르킨다.
		퀵정렬::swap(&A[b], &A[e]);
	}

	// 이제 피봇을 e의 자리와 변경하여 두 배열의 중앙에 위치하게 한다
	퀵정렬::swap(pivot, &A[e-1]);

	// 재귀함수로 좌우의 배열을 퀵정렬을 반복한다
	퀵정렬::QuickSort(A, begin, e - 2);
	퀵정렬::QuickSort(A, e, end);
}

크기가 8인 배열 [26, 32, 7, 1, 9, 17, 33, 36]을 정렬한다는 예제를 들어보자.

1. 중간 값을 찾기위해 원소 값 b = 26, m = 1, e = 36를 middle 함수에 보낸다.
2. middle함수에서 중간 값을 확인하여 반환한다. (26 반환)
3. 피봇을 배열의 첫 원소와 자리를 변경한다.
4. 피봇보다 큰 수를 순차적으로 탐색할 b와 피봇 보다 작은 수를 역순으로 탐색할 e를 선언한다.
5. b는 e를 넘지 않는 조건에서 피봇보다 큰 수를 탐색
6. e는 b보다 낮은 위치를 넘지 않는 조건에서 피봇보다 작은 수를 탐색
7. b와 e가 동일하지 않으면 두 위치의 원소를 서로 변경
   1. b와 e가 동일하면 동일한 원소이므로 변경하지 않아도 됨
8. 피봇을 중앙으로 위치를 변경
9. 피봇을 중심으로 더 작은 배열, 더 큰 배열을 따로 다시 퀵 정렬에 재귀 호출