[정렬알고리즘] Median of Three Quick Sort 중간 값 분할 빠른 정렬

대표적인 5가지 정렬 알고리즘을 직접 구현하고, 데이터 크기에 따른 성능을 비교하고 분석. 
알고리즘의 동작에 대한 분석 및 구현 코드의 설명.

Median of Three Quick Sort  _ 중간 값 분할 빠른 정렬

Quick Sort _ 빠른 정렬 : 하나의 큰 데이터를 두개의 작은 데이터로 분할하여 정렬하는 방법이다.

빠른 정렬은 분할과 정복 기법을 사용한 정렬이다. 빠른 정렬은 pivot 값을 선정하여 pivot 값을 중심으로 데이터를 pivot 보다 작은 값이 모여있는 부분과 큰 값이 모여있는 두 부분으로 나누게 된다. pivot을 중심으로 정렬 후에는 pivot은 데이터 셋에서 정확한 자신의 자리를 찾아서 들어가게 된다. 이로 인해 나눠진 두 데이터 셋은 다시 새로운 pivot 값을 선정하고 또다시 각자 두 부분으로 나눠지게 된다. 이와 같은 동작을 반복하여 정렬을 수행하게 된다.  

빠른 정렬의 경우 pivot 값을 중심으로 데이터가 계속 나눠질 때 재귀 호출을 하게 된다. n개의 원소를 정렬 할 때 걸리는 시간을 T_n 이라고 한다면, 빠른 정렬은 = 2  * T_(n/2)+2 , 즉 C_n = 2C_n + n으로 나타낼 수 있다. 이를 전개하면 나타내면 𝜃(nlogn)과 같이 나타내어 진다. 하지만 이는 평균적으로 나타내었을 때의 값이고, 최악의 경우는 O(n^2)까지 나타날 수 있다. 이는 이미 정렬된 데이터 값이 들어올 때 발생한다. 퀵 정렬은 stable 하진 않지만 별도의 저장 장소를 요구하지 않기 때문에 in-place 정렬이다. 

퀵 정렬의 성능을 향상시키기 위한 세가지 방법 중 이 과제에서는 pivot 값을 잘 선정하는 방법으로 성능을 향상시켰다. Median of Three 는 중간 값 분할을 사용한 것인데, 이는 왼쪽, 가운데, 오른쪽 값 중 중간 값을 선정하여 그 값을 pivot 값으로 사용하는 것이다. 이 방법을 사용하면 수행 시간의 약 5%를 감소시키고, 최악의 경우가 발생하는 확률을 낮추어 준다. 

 

Implementation

Swap 함수

모든 정렬 알고리즘에서 Swap 모듈을 사용하므로, 함수화 하여 사용한다. 

동적 배열의 주소 값과 정수 값 두개를 인자로 받고 첫번째 인자 a 와 두번째 인자 b를 index 로 하는 배열의 두 값을 바꿔주는 함수이다. 

void Swap(int* arr, int a, int b){
	int temp = arr[a];
	arr[a] = arr[b];
	arr[b] = temp;
}

Selection Sort

먼저 MoT Quick Sort 정렬 함수의 인자로는 동적 배열의 주소 값과 배열의 처음 인덱스와 마지막 인덱스를 받는다. 이는 처음 과 끝 인덱스를 사용하여 pivot 값을 정하고, 그 pivot 값을 중심으로 left 와 right 부분으로 나누어서 pivot 값과 비교하며 정렬을 수행하기 위함이다. 

중간 값 분할이기 때문에 원소가 세 개 일 때는 세 원소 중 중간 값을 찾는 Sort Three 함수를 이용하여 정렬할 수 있다. 

Sort Three 함수는 인자로 받은 세 인덱스의 원소 값들을 오름 차순 정렬하는 함수이다. 

원소가 세 개 이상일때부터 처음, 중간, 끝 값을 이용하여 중간 값을 찾고, 그 중간 값을 기준으로 Partition 함수로 분할하여 정렬하면 pivot의 정확한 위치를 찾게 된다. 이를 반복하면 정렬된 데이터를 얻을 수 있다. 

Partition 함수는 left, right, pivot 값을 인자로 받고, left는 pivot 값을 초과하면 멈추고, right 는 pivot 값을 초과하지 못하면 멈춘다. 이 때 두 값은 바뀌게 되며, 서로 엇갈릴 때까지 반복하게 된다. 이것을 반복하면 pivot 값을 중심으로 왼쪽은 pivot 값보다 작은 원소, 오른쪽은 pivot 값 보다 큰 원소들로 이루어진 두개의 파티션이 된다. 이때 함수는 엇갈렸을 때의 인덱스 값을 return한다. 이 값을 이용해 다시 Sort 함수에서 pivot 값을 찾고 정렬을 수행하게 된다. 

MoT Quick 함수는 메인 함수에서 호출되며, MoT Quick 정렬을 시작하고, 실행시간을 측정한다. 

class MoTQuickSorter{
public:
	void MoTQuickSort(int *arr, int start, int end){ //Median of Three Quick Sort
		int size = end-start+1;
		if(size == 1) return; //정렬할것이 없다면 return
		else if(size == 2){ //원소가 두개일때
			if(arr[start] > arr[end]) Swap(arr, start, end); //오름차순 정렬 1번만 실행한다. 
			return; //정렬할 필요 없다면 return 
		}else if(size == 3){ //원소가 세개일때
			SortThree(arr, start, end-1, end); //세개의 원소만 정렬하면 된다. 
		}else{ //원소가 세개 이상일때
			int pivIndex = (end+start) / 2, pivot; //median of three 처음, 중간, 끝 원소를 우선 정렬 시키기 위해 중간원소의 인덱스를 알아낸다. 
			SortThree(arr, start, pivIndex, end); //세개의 원소를 정렬하여 중간값을 찾는다. 
			pivot = arr[pivIndex]; //현재 pivot 값 저장
			int left = start, right = end; //leftㅇ와 right 초기화.
			left = Partition(arr, left, right, pivot); //partition 하여 얻어온 left값을 이용해 아래에서 재귀호출 한다. 
			//recursion
			if(start < left-1) MoTQuickSort(arr, start, left-1); //left part끼리 계속 Sort
			if(left < end) MoTQuickSort(arr, left, end); //right part끼리 계속 Sort
		}
	}
	int Partition(int *arr, int i, int j, int pivot){ //pivot값은 중아에있으므로 이에 맞춰 partion.
		int left= i, right = j;
		while(left <= right){ //엇갈릴때 까지
			while(left<=right && arr[left] < pivot) { left++; } //pivot 값을 초과하면 멈춘다
			while(left<=right && arr[right] > pivot) { right--; }//pivot 값을 초과하지못하면 멈춘다
			if( left <= right ){ //엇갈릴때까지
				Swap(arr, left, right); //멈춘 곳의 두 원소를 바꾼다. 
				left++; right--; //검사를 마친 인덱스는 넘어간다. 
			}
		} //엇갈렸다면 끝난다. 
		return left; //left 값을 리턴한다. 
	}
	void SortThree(int* arr, int a, int b, int c){ //세 원소를 오름차순으로 정렬한다. 
		if(arr[a] > arr[b]) Swap(arr, a, b); //첫째와 둘째 비교
		if(arr[b] > arr[c]) Swap(arr, b, c); //둘째와 셋째 비교
		if(arr[a] > arr[b]) Swap(arr, a, b); //다시 첫째와 둘째 비교 하면 3개 원소는 정렬이 끝이난다. 
	}
};

void MoTQuick(int* arr, int n){ //Median Of Quick Sort
	MoTQuickSorter mots;
	steady_clock::time_point start, end; nanoseconds result;
	start = steady_clock::now();
	//반복문을 사용하지 않고, 피봇값과의 비교로만 정렬이 이뤄지기 때문에 인덱스값(start와 end)를 넣어준다. 
	mots.MoTQuickSort(arr, 0, n-1); 

	end = steady_clock::now(); result = end - start;
	cout<<"2. Median of Three Quick Sort  : "<<result.count()<<"ns"<<endl; //알고리즘 실행시간
}