Quick Sort

Quick Sort 는 시간복잡도가 N log N 으로 Select, Bubble의 N^2 에 비해 확실히 빠르다.

Quick Sort는 Pivot 이라는 기준점을 기준으로 Left Right 에서 Pivot 으로 이동하면서 정렬하는 방식이다.

 

기준점인 Pivot을 선택하는데 있어서 첫 번째, 중간, 마지막, 랜덤 선택을 할 수가 있다.

본인은 중간을 선택하여 코딩을 해보았다. 한가지 방법을 알면 모두 적용이 가능하다.

L의 경우 Pivot 보다 큰 요소를 찾으며, 못 찾을 경우 L 을 증가시키며 Pivot과 R 에게 접근한다.

반대로, R의 경우 Pivot 보다 작은 요소를 찾으며, 못 찾을 경우 R을 감소시키며 Pivot과 L 에게 접근한다.

L 이 먼저 Pivot에 접근하면 범위를 늘리기 위해 R을 Pivot 으로 재설정 한다.

결국 L 이 R 을 만나면 while 루프를 빠져 나오게 된다.

마지막으로 Pivot을 교체하며 마무리한다.

그리고 재귀함수를 이용하여 return 한 Pivot을 기준으로 p-1, p+1 을 반복한다.

 

퀵 정렬이 빠른 이유

퀵 정렬 루프안에서 효율적으로 동작하도록 설계가 되어있기 때문이다.

그 이유는 메모리 참조가 지역화 되어있어서 CPU Cache 히트율이 높아진다.

Cache 는 메모리에 접근할 때, 주의 메모리 또한 자주 사용되어질 것이라 예상하고 MMU 에서 Cache로 인접한 메모리까지  참조하게 되는 것이다.

 

#include <stdio.h>

#define DATA_SIZE 10

int Partition(int data[], int nBegin, int nEnd)
{
	int L = nBegin;
	int R = nEnd;
	int Pivot = (int)((nBegin + nEnd) / 2.f);
	int Temp, i;
	
	while (L < R)
	{
		while ((data[L] < data[Pivot]) && (L < R)) L++;
		while ((data[R] >= data[Pivot]) && (L < R))	R--;
		
		if (L < R)
		{
			Temp = data[L];
			data[L] = data[R];
			data[R] = Temp;
		}

		if (Pivot == L)
			Pivot = R;
	}

	Temp = data[Pivot];
	data[Pivot] = data[R];
	data[R] = Temp;

	for (i = 0; i < DATA_SIZE; i++)
	{
		printf("%3d", data[i]);
	}
	printf("\n");

	return R;
}

void QuickSort(int data[], int nBegin, int nEnd)
{
	int p = Partition(data, nBegin, nEnd);
	
	Partition(data, nBegin, p - 1);
	Partition(data, p + 1, nEnd);
}

int main(void)
{
	int data[DATA_SIZE] = { 69, 2, 14, 15, 20, 75, 45, 34, 21, 99 };

	QuickSort(data, 0, DATA_SIZE - 1);

	getchar();

	return 0;
}

Cache 를 이용한 퀵정렬 결과이다.