[알고리즘] 퀵정렬(QuickSort)

안녕하세요. 꿈꾸는 개발자 몽키준입니다.

이번에는 퀵정렬에 대해 알아보려고 하는데요. 아시는 바와 같이 정렬방법은 여러가지가 있지만 그중에서 나름 괜찮은(?) 속도로 구현이 가능한 정렬 방법이 퀵 정렬인 것 같습니다. 가운데를 기준으로 좌우 대칭적인 값을 가지고 있는 데이터의 경우 가장 효과적으로 정렬이 가능(O(n l og n)합니다만 worst case 로는 O(n^2) 의 복잡도를 가집니다.

코드에 들어가기에 앞서 간략하게 동작원리를 설명하자면, 저장된 데이터 중 하나를 피봇으로 잡고 피봇 왼쪽에는 피봇보다 작은 값이 위치하도록 하고 피봇 오른쪽엔 피봇보다 큰값을 채워준다. 이를 무한히(데이터가 1개 인 경우) 반복하여 정렬 하는 방법입니다.

[퀵정렬 코드]

void printSrc(const char *str, int *src, int size)
{
	printf("%s : {", str);
	for (int i = 0; i < size; i++) {
		printf("%d ", src[i]);
	}	
	puts("}");
}

void swap(int *src1, int *src2)
{
	int tmp = 0;
	tmp = *src1;
	*src1 = *src2;
	*src2 = tmp;
}
/*
 pivot == left, and it gets left idx of smaller value than pivot 
 while getting right idx of larger value than pivot starting 
 from right.
 pivot  start of left     start of right
     |  |                  |
	 V  V                  v 
1st: 4, 1, 6, ..   ..., 5, 7}
     V     V      v
2nd: 4, 1, 6, ... 2, ..,5, 7} - swap
     V        V v
3th: 4, 1, 2, 8,3,6, ..,5, 7} - swap
     V       vV 
4th: 4, 1, 2, 3,8,6,...,5, 7} - swap(pivot, right)

5th: 3, 1, 2, 4,8,6 ...,5, 7} - return idx of right(3)

 */
int partition(int *src, int left, int right)
{
	int pivot = left;
	left++;
	while (left <= right) {
		while (src[left] <= src[pivot] && left < right) {
			left++;
		}
		while (src[right] >= src[pivot] && left <= right){
			right--;
		}

		if (left < right) {
			swap(&src[left], &src[right]);
		} else {
			break;
		}
	}
	swap(&src[pivot], &src[right]);
	return right;
}

void quickSort(int *src, int left, int right)
{
	if (left < right) {
		int idx = partition(src, left, right);
		quickSort(src, left, idx);
		quickSort(src, idx + 1, right);
	}
}

int main()
{
	int src[10] = {4, 1, 6, 8, 3, 2, 10, 9, 5, 7};
   	int size = 10;

	printSrc("Before", src, 10); 
	quickSort(src, 0, 10 - 1);
	printSrc("After", src, 10);
	return 0;
}