[ 자료구조 ] 정렬 - 04 . 퀵 정렬

[퀵 정렬]

[ 퀵 정렬 ]
퀵 정렬은 분할 정복 ( Divide and Conquer)에 기반한 알고리즘이다 .
퀵 정렬은 다음과 같은 과정의 분할정복으로 정렬을 수행한다 .

1. 데이터 집합 내에서 임의의 기준 요소를 선택하고 , 기준 요소보다 작은 요소들은 순서에 관계없이 무조건 기준 요소 왼편에 , 큰 값은 오른편에 위치한다 .
2. 기준 요소 왼편 / 오른편으로 나뉜 데이터 집합 내에서 다시 1의 과정을 반복한다 .
3. 더이상 데이터 집합을 나눌 수 없을때까지 반복하면 정렬된 데이터 집합을 얻게 된다 .

[ 기준 요소의 선택 ]
퀵 정렬이 더 빠른 성능을 갖게 하는 개선사항 중 하나는 데이터 집합 내에서 좋은 기준요소를 선택하는 것이다 .

무작위로 기준 요소를 선택하는 것은 최소 / 최대 값이 선택되는 확률을 크게 줄일 수 있지만 , 난수를 추출하는 과정에서
성능저하가 생길 수 있어 좋은 방법은 아니다 .

더 좋은 방법은 처음 데이터 집합의 처음 세개 요소중 중간 값을 기준요소로 지정하는 것이다 .중간값을 구하는 작은 성능 비용이 지출되지만 최악의 경우는 항상 피할 수 있다 .

[퀵 정렬 구현의 문제]

[ 배열 사용 문제 ]
배열은 링크드 리스트처럼 삽입 , 삭제가 자유롭지 못해 분할의 수행이 어렵다 .
이에 2명의 정찰병으로 수색 섬멸을 사용하려 한다 .

첫번째 정찰병은 왼쪽부터 오른쪽으로 이동하며 기준보다 큰 요소를 찾고
두번째 정찰병은 오른쪽부터 기준보다 작은 요소를 찾는다 . 두 정찰병이 찾은 요소를 교환한다 .
정찰병은 서로 접선할때까지 검사를 진행하고 , 접선하면 기준요소를 왼쪽 데이터 집합의 마지막 요소와 교환한다 .

[ 반복되는 분할과정의 처리 ]
재귀호출을 통해 반복되는 분할 과정을 처리한다 . 코드는 다음과 같다 .

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 );
    }
}

[퀵 정렬 구현]

[ QuickSort.cpp ]

#include<stdio.h>

//두 수를 교환한다
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;
		//기준보다 작은 요소를 찾을때까지 반복
		while (DataSet[Right] > Pivot)
			--Right;

		//두 요소가 만난다면 (최종으로 바꾸고 난 후) 중단한다
		if (Left >= Right)
			break;
		//두 요소를 바꾸어준다
		Swap(&DataSet[Left], &DataSet[Right]);
	}
	//(--해서 Right가 왼쪽 데이터 집합의 마지막 요소이다)
	//기준 요소와 왼쪽 집단의 마지막 요소를 교환하면 분류 완료!
	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,5,4,3,2,1 };
	int Length = sizeof DataSet / sizeof(DataSet[0]);
	int i = 0;
	QuickSort(DataSet, 0, Length-1);

	for (i = 0; i < Length; i++)
	{
		printf("%d\t", DataSet[i]);
	}
	printf("\n");
	return 0;
}

[퀵 정렬의 성능 ]

[ 퀵정렬의 성능 분석 ]
앞서 다룬 버블 정렬 / 삽입 정렬은 비교횟수와 데이터 집합을 순회하는 반복 횟수를 이용해서 성능 분석을 하였다 .
퀵 정렬은 비교횟수와 재귀 호출의 깊이를 이용하여 성능을 분석한다 .

• 퀵 정렬의 재귀 호출 깊이
• 데이터 집합을 나누기 위해 필요한 비교 횟수

[ 최선의 경우 ]
퀵 정렬은 데이터 집합이 어떻게 정렬되어 있는지가 성능을 좌우하는 알고리즘 이다 .
데이터가 미리 정렬되어 있거나 / 역순으로 정렬되어 있다면 최악의 성능을 보이지만
데이터가 이리 저리 흩어져 있다면 최고의 성능을 보인다 .

재귀 호출의 깊이

=>가장 최선은 퀵 정렬의 호출때마다 데이터 집합이 1/2로 쪼개지는 상황이다 .
해당 상황에서 16개의 집합을 만들어야 한다면 4단계를 ,32 개의 집합은 5단계를 거친다 .
즉 , 데이터의 개수가 n개라면 퀵 정렬의 재귀 호출 깊이는 log 2n 이다 .

cf)1000=10의 n승은 을 로그로 표현한다면 n=log 10 1000으로 표현한다 .
이를 10을 밑으로 하는 1000의 로그라고 표현한다 .

비교횟수
=>재귀 호출의 첫 단계에서 수행하는 비교는 n회이다 .
두번째 역시 n/2+n/2 이며 세번째도 n/4 + n/4 + n/4 + n/4이다 . 즉 , 각 재귀호출에서 비교회수는 n회임을 알 수 있다 .
각 단계에서 쪼개져 있는 데이터 집합의 크기를 합하면 항상 n개이기 때문이다 .

결론
=>이상적인 경우의 퀵 정렬의 비교 횟수
=재귀호출의 깊이 X 각 재귀 호출 단계에서의 비교 횟수
= N X log2N = N log2N이다 .

[ 최악의 경우 ]
재귀 호출의 깊이

=>최악의 경우는 데이터 집합의 분할이 1:n-1로 수행되는 상황이다

비교횟수
=>재귀 호출이 일어날때마다 정렬 대상의 범위도 1씩 줄어든다 . 비교횟수는 다음과 같이 정의된다 .
(n-1)+(n-2)+ .. 3+2+1 = n * (n-1)/2이다 .

결론
=>이상적인 경우의 퀵 정렬의 비교 횟수
=재귀호출의 깊이 X 각 재귀

[ 평균의 경우 ]
퀵 정렬은 특별한 일이 없는 한 평소에 좋은 성능을 보여준다 . 퀵 정렬은 평균적으로 1.39nlog2n회의 연산을 수행하며 이는nlog2n의 최선보다 39% 정도만 느린 상태이다.