[#10] Quick Sort : 퀵 정렬

퀵  정렬

O(n log2 n)

퀵 정렬을 사용할 때 가장 이상적인 경우의 수이다. 이진 탐색의 형태처럼 데이터들이 쪼개지며 비교연산한다. n log2n의 의미는 재귀 호출의 깊이 * 재귀 호출에서 비교 탐색하는 요소의 개수(비교 개수) 이다.

 

퀵 정렬은 특정한 요소 T를 기준으로 두 갈래로 나누어서 탐색을 하게 된다. 두 갈래를 각자 A와 B라고 한다면 A는 기준이 되는 요소 T가 속한 인덱스를 기점으로 점점 증가하며 T보다 큰 수를 찾는다. B는 T보다 작은 수를 찾아가며 인덱스가 감소한다. 만약 A와 B가 비교에 적합한 수를 찾았을 경우 Swap을 하고 결국 만나게되면 하나의 재귀 호출에서 비교가 끝나게 된다. 즉 이러한 비교는 n / 2 + n / 2 = n    n / 4 + n / 4 + n / 4 + n / 4 = n  처럼 비교해야할 요소가 기하급수적으로 감소하므로 결국 재귀의 깊이와 상관없이 무조건 n에 수렴하기 때문에  n * log2n이 된다. 

 

평균 1.39 * n * log2n

대부분의 경우 퀵 정렬이 사용될 때는 평균적으로 nlog2n 보다 39% 정도 느리게 동작한다.

 

최악의 경우

최악의 경우로 주어진 데이터의 정렬이 역수일 경우 n(n-1)/2이다. 이는 버블 정렬과 동일하다.

 

 

---

 

 

전체 코드

퀵 정렬

#include <iostream>

void Swap(int* A, int* B)
{
	int temp = *A;
	*A = *B;
	*B = temp;
}

int Partition(int DataSet[], int Left, int Right)
{
	int First = Left;
	int Pivot = DataSet[First];
	++Left;

	while (Left <= Right)
	{
		while (DataSet[Left] <= Pivot && Left < Right)
			++Left;
		while (DataSet[Right] > Pivot && Left <= Right)
			--Right;

		if (Left < Right)
			Swap(&DataSet[Left], &DataSet[Right]);
		else
			break;
	}

	Swap(&DataSet[First], &DataSet[Right]);
	return Right;
}

void QuickSort(int DataSet[], int Left, int Right)
{
	if (Left < Right)
	{
		int Index = Partition(DataSet, Left, Right);
		QuickSort(DataSet, Left, Index - 1);
		QuickSort(DataSet, Index + 1, Right);
	}
}

int main(void)
{
	int DataSet[] = { 6, 4 ,2, 3, 1, 5 };
	int size = sizeof DataSet / sizeof DataSet[0];

	QuickSort(DataSet, 0, size - 1);

	for (int i = 0; i < size; i++)
		std::cout << DataSet[i] << ' ';
	std::cout << std::endl;

	return 0;
}

 

 

 

qsort() 라이브러리 함수 사용 

#include <iostream>
#include <cstdlib>
#include <cstring>

/*
void qsort(
	void *base,    // 데이터 배열 주소
	size_t num,    // 데이터 요소 개수
	size_t width,  // 데이터 요소 바이트 크기
	int (___cdecl *compar)(const void*, const void*) // 함수 포인터
)*/

// < 0, return -1
// = 0, return 0
// > 0, return Positive numbers
int CompareScore(const void* _elem1, const void* _elem2)
{
	char elem1 = *(char*)_elem1;
	char elem2 = *(char*)_elem2;

	// 소문자일 경우 비교를 위해서 대문자로 변환
	if (elem1 >= 'a')
		elem1 -= 32;
	if (elem2 >= 'a')
		elem2 -= 32;

	if (elem1 > elem2)
		return 1;
	else if (elem1 == elem2)
		return 0;
	else if (elem1 < elem2)
		return -1;
}

int main(void)
{
	char DataSet[] = { 'S', 'a', 'B', 'd', 'F', 'E'};
	int Length = sizeof DataSet / sizeof DataSet[0];
	int i = 0;

	// 함수 원형 = int compare((void*)& elem1, (void*)& elem2);
	qsort((char*)DataSet, Length, sizeof (char), CompareScore);

	for (i = 0; i < Length; i++)
		std::cout << DataSet[i] << ' ';
	std::cout << std::endl;

	return 0;
}

 

---