[알고리즘/C] 퀵 정렬(quicksort)

 

퀵 정렬이란?

퀵 정렬(quicksort)은 평균적으로 빠른 수행 속도를 자랑하는 정렬 방법이다. 퀵 정렬 또한 분할-정복법에 근거한다. 2개의 부분 리스트로 분할한 후 각각의 부분 리스트를 다시 퀵 정렬한다. 그러나 리스트를 비균등하게 분할한다.

먼저, 리스트의 한 요소를 피봇(pivot)으로 선택한다. (여기서는 마지막 요소를 선택한 경우와 첫 번째 요소를 선택한 경우를 다룬다.) 피봇보다 작은 요소들은 모두 피봇의 왼쪽으로 옮겨지고, 피봇보다 큰 요소는 모두 피봇의 오른쪽으로 옮겨진다. 이 상태에서 피봇을 제외한 왼쪽 리스트와 오른쪽 리스트를 각각 정렬하면 전체 리스트가 정렬된다.

 

맨 마지막 요소를 pivot으로 하는 경우 - 첫번째 알고리즘

i는 left-1부터, j는 left부터 시작하여 이동한다. j는 pivot보다 작을 때까지 이동하고, 찾으면 i가 가리키는 다음 수와 j가 가리키는 수를 교환하고, 이 때 i는 오른쪽으로 이동한다.. 이 과정을 반복하고 j가 pivot의 위치에 도달하면 i의 다음 위치에 있는 수와 pivot을 교환하고, i의 다음 위치 인덱스를 반환한다.

 

void swap(int A[], int i, int j) {
	int temp = A[j];
	A[j] = A[i];
	A[i] = temp;
}

int partition(int A[], int left, int right) {
	int i = left - 1;
	int j = left;
	int pivot = A[right];

	while (j < right) {
		if (A[j] < pivot) { //A[j]가 pivot보다 작으면,
			swap(A, ++i, j); //i가 가리키는 다음 수와 j가 가리키는 수를 서로 바꾸고 i 전진
		}
		j++;
	}
	swap(A, ++i, right); //j==r이면, i가 가리키는 다음 수와 pivot의 위치를 바꿈

	return i; //새로운 pivot의 위치 반환
}

void quick_sort(int list[], int low, int high) {
	int q;
	
	if (p < r) {
		q = partition(list, low, high);
		quick_sort(list, low, q - 1); //pivot의 왼쪽 정렬
		quick_sort(list, q + 1, high); //pivot의 오른쪽 정렬
	}
}

 

 

 

맨 마지막 요소를 pivot으로 한 경우 - 두 번째 알고리즘

i는 left-1부터 시작하고, j는 right부터 시작한다. i는 pivot보다 큰 수를 찾을때까지 오른쪽으로 이동하고, j는 pivot보다 작은 수를 찾을때까지 왼쪽으로 이동한다. 그리고 i와 j 두개가 멈출때 그때의 수를 서로 교환한다. 이 과정을 반복하면서 j가 i가 작아지는 순간 i 자리에 있는 수와 pivot을 교환하고, i를 반환한다.

 

void swap(int A[], int i, int j) {
	int temp = A[j];
	A[j] = A[i];
	A[i] = temp;
}

//마지막 요소가 pivot이고 i는 왼쪽에서 오른쪽, j는 오른쪽에서 왼쪽으로 움직일때
int partition(int A[], int left, int right) {
	int i = left - 1;
	int j = right;
	int pivot = A[right];
	
	do {
		do
			i++;
		while (A[i] < pivot); //pivot보다 큰 수의 i 찾기
		do
			j--;
		while (A[j] > pivot); //pivot보다 작은 수의 j찾기
		if (i<j) swap(A, i, j);
	} while (i < j);

	swap(A, i, right);
	return i;
}

void quick_sort(int list[], int low, int high) {
	int q;
	
	if (low < high) {
		q = partition(list, low, high);
		quick_sort(list, low, q - 1); //pivot의 왼쪽 정렬
		quick_sort(list, q + 1, high); //pivot의 오른쪽 정렬
	}
}

 

 

맨 첫번째 요소를 pivot으로 하는 경우 - 첫번째 알고리즘

pivot의 위치가 달라지는 것 빼고는 원리는 같다.

 

void swap(int A[], int i, int j) {
	int temp = A[j];
	A[j] = A[i];
	A[i] = temp;
}

int partition(int A[], int left, int right) {
	int i = left;
	int j = left + 1;
	int pivot = A[left];

	while (j <= right) {
		if (A[j] < pivot) { //A[j]가 pivot보다 작으면,
			swap(A, ++i, j); //i가 가리키는 다음 수와 j가 가리키는 수를 서로 바꾸고 i 전진
		}
		j++;
	}
	swap(A, i, left); //j==r이면, i가 가리키는 수와 pivot의 위치를 바꿈

	return i; //새로운 pivot의 위치 반환
}

void quick_sort(int list[], int low, int high) {
	int q;
	
	if (low < high) {
		q = partition(list, low, high);
		quick_sort(list, low, q - 1); //pivot의 왼쪽 정렬
		quick_sort(list, q + 1, high); //pivot의 오른쪽 정렬
	}
}

 

 

맨 첫번째 요소를 pivot으로 하는 경우 - 두번째 알고리즘

pivot의 위치가 달라지는 것 빼고는 원리는 같다.

 

void swap(int A[], int i, int j) {
	int temp = A[j];
	A[j] = A[i];
	A[i] = temp;
}

int partition(int A[], int left, int right) {
	int i = left;
	int j = right + 1;
	int pivot = A[left];

	do {
		do
			i++;
		while (A[i] < pivot); //pivot보다 큰 수의 i 찾기
		do
			j--;
		while (A[j] > pivot); //pivot보다 작은 수의 j찾기
		if (i<j) swap(A, i, j);
	} while (i < j);

	swap(A, j, left);

	return j;
}

void quick_sort(int list[], int low, int high) {
	int q;
	
	if (low < high) {
		q = partition(list, low, high);
		quick_sort(list, low, q - 1); //pivot의 왼쪽 정렬
		quick_sort(list, q + 1, high); //pivot의 오른쪽 정렬
	}
}

 

 

시간복잡도

 

• 평균적인 경우 : 퀵 정렬은 합병정렬과 같이 리스트를 분할하므로 패스의 횟수를 k라고 하면 $$k={log}_{2}n$$ 이다. 그리고 각 패스에서 전체 리스트의 대부분의 레코드를 비교하므로 평균 n번의 비교 연산이 이루어지므로, 시간 복잡도는 $$O(n{log}_{2}n)$$ 이다.
• 최악의 경우 : 이미 정렬된 리스트일 경우, 계속 불균형하게 나누어지므로 퀵 정렬의 패스의 개수는 n이 되고 한번의 패스마다 평균 n번의 비교 연산이 필요하므로 $$O(n^2)$$이다.
• 퀵 정렬은 추가 메모리 공간이 필요하지 않고 불필요한 데이터의 이동을 줄이고, 한번 결정된 피벗들이 추후 연산에서 제외되기때문에 빠른 정렬 방법이다.
• 그러나, 이미 정렬된 리스트일 경우에 수행시간이 더 많이 걸리는 단점이 있다.
• 따라서, 불균형 분할을 방지하기 위해 피봇을 선택할 때 왼쪽이나 오른쪽 데이터를 사용하는 대신에 중앙값을 피봇으로 선택하는 것이 바람직하다.