[퀵소트 구현] 퀵소트 구현, 최악의 케이스 직접 확인

퀵소트는 평균 시간복잡도가 nlogn인 알고리즘이지만 최악의 경우의는 n^2 의 시간복잡도를 가진다고 한다.

 

최악의 케이스를 가지는 경우는 배열이 이미 정렬되어있는 경우이다.

 

이 때, 배열이 오름차순으로 정렬되어있든, 내림차순으로 정렬되어있든 상관없다. 마찬가지로 배열이 모두 같은 값을 가진다고 해도 적용이 된다. 만약 모두 10이라는 값을 가지고 있는 배열도 이미 정렬되어있는 배열이나 마찬가지이기 때문이다.

 

1. 시간복잡도 계산법

간단하게 생각해서 n개의 데이터에 대해 divde&conquer를 몇번 수행하느냐만 알면 된다. 

평균적으로 divide&conquer가 log(n)번 수행되기 때문에 퀵소트의 평균 시간복잡도가 nlog(n)인 것이다.

 

그런데 최악의 경우에는 divide&conquer가 log(n)번이 아니라 n번 수행된다. 이는 퀵소트로 인한 배열의 변화를 직접 종이에 써서 확인해볼 수 있다. 직접 확인해보면 최악의 케이스는 공통적으로 divide 단계에서 구간이 pivot을 기준으로 2구간으로 나뉘는것이 아니라 1구간으로만 나뉘는것을 확인할 수 있다. 매번 1개의 구간으로만 나뉘기 때문에 divide&conquer를 n번 수행하게 되는것이다. 만약 매번 2개의 구간으로 나뉜다면 직관적으로도 log(n)번 수행된다는 것을 알 수 있다.

 

 

2. 최악의 case에 걸리지 않게하기 위한 해결법은?

1) 가장 간단한 방법은 배열이 정렬되어있지 않게 하는것이다. 즉, 퀵소트 알고리즘 시행전에 배열을 무작위로 shuffle한다.

2) pivot을 랜덤하게 선택하는 것이다. 매 구간마다 가장 앞의 수를 고르거나 가장 뒤의 수를 pivot으로 선정하게 되면 당연히 정렬되어있는 배열에서는 최악의 케이스를 맞이할 수 밖에 없다.

3) 값을 랜덤하게 3개 골라서 그 중 중간값을 pivot으로 선정하는 것이다. 이 방법은 최악의 케이스를 반드시 피할 수 있으나, 차악의 케이스를 선택하게 될 수도 있다.(물론 고르는 3개의 값을 랜덤하게 고르면 확률은 지극히 낮을 것이다.)

 

 

아래는 기본적인 퀵소트를 직접 구현한 코드이다.

 

#include <iostream>
#include <time.h>
using namespace std;

#define SIZE 10000
void divide(int arr[], int l, int r, int pivot);
void Swap(int *first, int *second);
void Conquer(int arr[], int l, int r);
void quickSort(int arr[], int l, int r);

void Swap(int *first, int *second)
{
	int tmp = *first;
	*first = *second;
	*second = tmp;
}
void divide(int arr[], int l, int r, int pivot)
{
	Conquer(arr, l, pivot - 1);
	Conquer(arr, pivot + 1, r);
}

void Conquer(int arr[], int l, int r)
{
	if (l < r)
	{
		int pivot = l;
		int i = pivot + 1;
		int j = r;

		while (i <= j)
		{
			while (pivot < j && arr[pivot] <= arr[j])
			{
				j--;
			}
			while (i < j && arr[pivot] >= arr[i])
			{
				i++;
			}

			if (i < j)
			{
				Swap(&arr[i], &arr[j]);
			}
			else if (i >= j)
			{
				Swap(&arr[pivot], &arr[j]);
				break;
			}
		}

		divide(arr, l, r, j); // 여기서 j == pivot
	}
}
void quickSort(int arr[], int l, int r)
{
	Conquer(arr, l, r);
}

int main()
{
	//int array[10] = { 3,2,1,1,4,4,9,9,9,6 };
	int arrRand[SIZE];
	int arrSort[SIZE];
	
	for (int i = 0; i < SIZE; i++)
	{
		arrRand[i] = rand() % 100; // 난수로 생성한 배열
	}
	
	for (int i = 0; i < SIZE; i++)
	{
		arrSort[i] = i;	// 정렬되게 생성한 배열
	}

	clock_t start;
	start = clock();	// 시간 재기 시작
	quickSort(arrRand, 0, SIZE-1); // 난수배열 소팅
	printf("난수배열 걸린시간 : %.3lf\n", (double)(clock() - start));	// 걸린 시간 출력(ms)

	start = clock();	// 시간 재기 시작
	quickSort(arrSort, 0, SIZE-1); // 난수배열 소팅
	printf("정렬배열 걸린시간 : %.3lf\n", (double)(clock() - start));	// 걸린 시간 출력(ms)

	return 0;
}