분할 정복 알고리즘 - Quick Sort

 

-방법

1)배열의 원소 하나를 피봇(pivot)삼고 기준

2)피봇보다 작은 숫자들은 왼쪽, 피봇보다 큰 숫자들은 오른쪽에 위치하도록 분할

3)분할된 부분문제에 대해서도 위와 동일한 과정을 재귀적으로 수행하여 정렬

+이 때, 피봇은 분할된 왼편이나 오른편 부분에 포함되지 않는다. 

 

-Pseudo Code

QuickSort(A, left, right)
입력: 배열 A[left]~A[right]
출력: 정렬된 배열 A[left]~A[right]
1. if (left < right) {//배열 A의 가장 왼쪽 원소의 인덱스가 가장 오른쪽 원소의 인덱스보다 작으면, 정렬 수행. 그렇지 않으면 1개의 원소를 정렬하는 경우임. 
2. 피봇을 A[left]~A[right] 중에서 선택하고, 피봇을 A[left]와 자리를 바꾼 후, 피봇과 각 원소를 비교. 피봇보다 작은 숫자:A[left]~A[p-1] 피봇보다 큰 숫자:A[p+1]~A[right] 피봇: A[p]
3. QuickSort(A, left, p-1) // 피봇보다 작은 그룹
4. QuickSort(A, p+1 right) // 피봇보다 큰 그룹

 

-Time Complexity

퀵 정렬의 성능은 어떤 피봇을 선택하느냐에 따라 달라진다.

 

1.피봇으로 항상 가장 작은 숫자가 선택될 경우(worst)

->한 번에 숫자 하나씩만 정렬되고, recursion을 n번 해야한다.

->n-1 걸리는 비교가 n번 일어남 =>O(n^2)

 

2.중간의 값을 피봇으로 선정한 경우(best)

->한 번에 전체의 1/2이 정렬된다. recursion을 log₂n번 해야한다.

->n-1 걸리는 비교가 log2n번 일어남 =>O(nlogn)

 

3.결론. 평균 경우 시간복잡도

->피봇을 항상 랜덤하게 선택한다고 가정하면, 평균으로 시간 복잡도를 계산한다.

=>O(nlogn)

 

-소스코드

#include <stdio.h>
#include <stdlib.h>
#define SIZE 12

void QuickSort(int* A, int left, int right) {
	if (left < right) {//배열의 원소의 수가 2개 이상이면
		int p, temp;

		p = (left + right) / 2 + 1;//피봇 선택. 중간 원소의 인덱스로 선택했다.
		temp = A[left];
		A[left] = A[p];
		A[p] = temp;//피봇을 A[left]와 자리를 바꾼다.

		//A[left]와 A[p+1]~A[right]를 비교한다.
		int i = left + 1;//배열의 원소를 하나씩 비교한다. i는 피봇보다 큰 값을 찾는다.
		int j = right;//j는 피봇보다 작은 값을 찾는다.

		while (i <= j) {//왼쪽과 오른쪽에서 시작한 i, j가 만나게 되면 비교 종료한다.
			while (A[i] <= A[left] && i <= right)//피봇보다 작은 값이면 넘어감
				i++;
			while (A[j] >= A[left] && j > left)//피봇보다 큰 값이면 넘어감
				j--;
			if (i > j) {//i와 j가 엇갈리면 피봇 알맞은 위치로 바꿔줌
				temp = A[j];
				A[j] = A[left];
				A[left] = temp;
			}
			else {//i번째 값과 j번째 값의 자리를 바꾼다.
				temp = A[j];
				A[j] = A[i];
				A[i] = temp;
			}
			for (int i = 0; i < SIZE; i++) {
				printf(" %d  ", A[i]);
			}
			printf("\n");
		}
		QuickSort(A, left, j - 1);//피봇보다 작은 그룹
		QuickSort(A, j + 1, right);//피봇보다 큰 그룹
	}
}

int main() {
	int n = SIZE;
	int a[] = { 6,3,11,9,12,2,8,15,18,10,7,14 };

	printf("Before Sorting:");
	for (int i = 0; i < SIZE; i++) {
		printf(" %d  ", a[i]);
	}
	printf("\n");
	QuickSort(a, 0, n - 1);
	printf("\nAfter Sorting: ");
	for (int i = 0; i < SIZE; i++) {
		printf(" %d  ", a[i]);
	}
	return 0;

}

실행 결과

코드 이해는 쉽지만  그림으로 따라가려니 복잡한 알고리즘이었다.