2-(2) QuickSort

이 챕터는 Sorting의 한 방법인 Quick Sort에 대해 배운다. Average case의 Time Complexity 증명은 생략하지만, Worst case n²에 average case nlgn인 알고리즘이라고 생각하면 될 것 같다. worst case의 증명은 쉬우니까 알고리즘을 설명하고 한 번 하고 가겠다.

 

(1) QuickSort Algorithm의 설명

QuickSort algorithm은 다음과 같은 재귀적 알고리즘이다.

(i) 배열의 원소 중 하나의 원소를 골라 Pivot으로 선정한다.

(-->이 Pivot선정을 Randomize시켜야 average nlgn이 나온다.)

(ii)그 Pivot보다 작은 놈들을 Pivot왼쪽에, 큰 놈들을 Pivot오른쪽에 놓는다.(called Partition) Pivot은 q번째 위치에 왔다고 해보자.

(iii)그러면 Pivot은 q번째로 작은 수이다.(왜냐면 pivot보다 작은 놈이 q-1개 나머지는 큰 놈이니까)

(iv)따라서 pivot은 적절한 위치에 왔다고 볼 수 있고 왼쪽과 오른쪽 sub array만 정렬하면 된다.

(v)따라서 recursively 왼쪽과 오른쪽의 subarray에 대해 콜한다.

이 과정을 코드로 나타내보면 다음과 같다.

void QuickSort(int* arr, int p,int r) {
	if (p < r) {
		int q = Partition(arr, p, r);
		QuickSort(arr, p, q - 1);
		QuickSort(arr, q + 1, r);
	}

}

퀵 소트 자체 구현은 쉽다. 문제는 Partition과정이다.

 

(2) Partition 과정의 구현

Partition은 위의 그림과 같은 형식으로 구현할 것인데, 우선 주어진 배열의 마지막 원소인 arr[r]을 pivot으로 선정하고  j라는 iterator를 p부터 r-1까지 움직일 것이다. 그리고 다음과 같은 비교를 한다.

(i)arr[j]가 pivot보다 크다면 그냥 j만 증가시킨다.

(ii)arr[j]가 pivot보다 작다면 i를 1 증가시킨 뒤 arr[i]와 arr[j]를 교환한다.

이 과정을 i=p-1로 초기화 한 뒤 반복하게 한다면 arr[i]까지는 pivot보다 작은놈 arr[i+1]~arr[r]은 pivot보다 큰 놈만 있는 상황이 될 것이다.

그러면 arr[i] 바로 뒤가 pivot이 들어갈 자리가 되므로 arr[i+1]과 arr[r]을 swap하면 partition의 역할이 끝난다. 밑은 Partition 코드다.

int Partition(int* arr, int p, int r) {
	int pivot = arr[r];
	//last element is pivot
	
	int i = p-1; //i+1번째부터 pivot보다 큰 원소들이라고 생각
	
	for (int j = p; j < r; j++) {
		if (arr[j] < pivot) 
			swapPos(arr[++i], arr[j]);
	}
	
	swap(arr[i + 1], arr[r]);
	return (i + 1);
	
}

테스트 코드를 포함한 전체 코드는 다음과 같다.

#include<iostream>
#include<time.h>
using namespace std;

void swapPos(int& arr1, int& arr2) {
	int temp = arr1;
	arr1 = arr2;
	arr2 = temp;
}

int Partition(int* arr, int p, int r) {
	int pivot = arr[r];
	//last element is pivot
	
	int i = p-1; //i+1번째부터 pivot보다 큰 원소들이라고 생각
	
	for (int j = p; j < r; j++) {
		if (arr[j] < pivot) 
			swapPos(arr[++i], arr[j]);
	}
	
	swap(arr[i + 1], arr[r]);
	return (i + 1);
	
}

void QuickSort(int* arr, int p,int r) {
	if (p < r) {
		int q = Partition(arr, p, r);
		QuickSort(arr, p, q - 1);
		QuickSort(arr, q + 1, r);
	}

}



bool Issort(int* arr, int size) {
	
	for (int i = 0; i < size - 1; i++) {
		if (arr[i] > arr[i + 1]) return false;
	}
	return true;

}





int main() {
	int arrsize;
	cout << "Enter size of array: ";
	cin >> arrsize;
	const int range = 10000;
	int* arr = new int[arrsize];
	double m_ratio = 0.5;	//Change the ratio of negative numbers
	srand((unsigned int)time(NULL));
	for (int i = 0; i < arrsize; i++)
	{
		arr[i] = rand() % range - int(m_ratio * range);
	}


	QuickSort(arr, 0, arrsize - 1);
	cout << ((Issort(arr, arrsize)) ? "success" : "false")<<endl;
	for (int i = 0; i < arrsize;i++) 
		cout << "arr[" << i << "]: " << arr[i]<<endl;
}

Time complexity생각해보면 Quick Sort은 Partition + recursive call이다. 따라서 

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

꼴이 되어서 q가 어디 잘 잡히는지에 의해 복잡도는 바뀔 것이다.

(n은 partition하는데 j가 움직이는 시간)

풀어보면 q가 극단적(p or r)인 경우가 계속 걸릴 때는 n²이 되고 평균적으로는 nlogn이 걸린다고 한다.