[간단 정리] 퀵 정렬

*오름차순 기준입니다

 

정렬 알고리즘 중에 퀵 정렬이 가장 성능이 좋다. 다른 원소와 비교하여 정렬을 수행하는 비교 정렬에 속한다. 최악의 시간 복잡도는 O(N^2)이지만 최선과 평균이 O(NlogN)이다. 원소들 중에 같은 값이 있으면 순서가 달라질 수 있기 때문에 불안정 정렬이다.

 

기본적인 동작

1. 배열 중에 하나의 원소를 골라 피벗(기준)을 정한다.

2. 피벗을 기준으로 앞에는 피벗보다 작은 값, 뒤에는 큰 값이 오도록 나눈다. 이를 분할이라고 한다.

3. 분할된 배열에 대해 위 과정을 재귀적으로 반복한다.

 

최악의 경우는 피봇으로 가장 작은 수가 선택되거나 큰 수가 선택될 때인데, 이는 중위값을 선정해 해결할 수 있다. 0번째, 가운데, 마지막 요소 중에서 중간 값을 피벗으로 정하면 된다. 퀵 정렬의 핵심은 피벗을 중심으로 값을 분류하는 것이다. 구현에서는 이 역할을 Partition이라는 함수가 수행한다. MedianOf3 함수에서 중위값인 피봇은 left보다 크고 right보다 작으며 right-1의 위치에 스왑된다. 때문에 Partition에서 피벗과 값 비교를 할 때 첫 번째 요소와 right, right - 1과는 비교하지 않는다.

 

>>구현

#include <cstdio>
#include <cstdlib>

void PrintArr(int arr[], int size);
void QuickSort(int intArray[], int left, int right);
int MedianOf3(int intArray[], int left, int right);
void Swap(int intArray[], int dex1, int dex2);
int Partition(int intArray[], int left, int right, double pivot);
void ManualSort(int intArray[], int left, int right);

int main()
{
	int intArray[] = { 1, 9, 2, 8, 3, 7, 4, 6, 5 };
	PrintArr(intArray, 9);
	QuickSort(intArray, 0, _countof(intArray) - 1);
	PrintArr(intArray, 9);
}

void PrintArr(int arr[], int size)
{
	for (int i = 0; i < size; ++i)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}

void QuickSort(int intArray[], int left, int right)
{
	int size = right - left + 1;
	if (size <= 3)
		ManualSort(intArray, left, right);
	else 
	{
		double median = MedianOf3(intArray, left, right);
		int partition = Partition(intArray, left, right, median);
		QuickSort(intArray, left, partition - 1);
		QuickSort(intArray, partition + 1, right);
	}
}

int Partition(int intArray[], int left, int right, double pivot)
{
	int leftPtr = left;
	int rightPtr = right - 1;

	while (true)
	{
		while (intArray[++leftPtr] < pivot);
		while (intArray[--rightPtr] > pivot);
		if (leftPtr >= rightPtr)
			break;
		else
			Swap(intArray, leftPtr, rightPtr);
	}
	Swap(intArray, leftPtr, right - 1);
	return leftPtr;
}

// gurantee right is the biggest value in left, center, right.
// and pivot is located to (right-1)
int MedianOf3(int intArray[], int left, int right)
{
	int center = (left + right) / 2;

	if (intArray[left] > intArray[center])
		Swap(intArray, left, center);

	if (intArray[left] > intArray[right])
		Swap(intArray, left, right);

	if (intArray[center] > intArray[right])
		Swap(intArray, center, right);

	Swap(intArray, center, right - 1);
	return intArray[right - 1];
}

void Swap(int intArray[], int dex1, int dex2)
{
	int temp = intArray[dex1];
	intArray[dex1] = intArray[dex2];
	intArray[dex2] = temp;
}

void ManualSort(int intArray[], int left, int right)
{
	int size = right - left + 1;
	if (size <= 1)
		return;
	if (size == 2) 
	{
		if (intArray[left] > intArray[right])
			Swap(intArray, left, right);
		return;
	}
	else 
	{
		if (intArray[left] > intArray[right - 1])
			Swap(intArray, left, right - 1);
		if (intArray[left] > intArray[right])
			Swap(intArray, left, right);
		if (intArray[right - 1] > intArray[right])
			Swap(intArray, right - 1, right);
	}
}