개요

리스트에서 k번째로 작은(혹은 큰) 요소를 찾는 알고리즘

정렬을 하지 않고도 효율적으로 요소를 찾는 것이 목적이다

전략

Selection 알고리즘은 피봇을 기준으로 리스트를 분할하고 피봇의 위치를 기준으로 k번째 값의 위치를 구하고 분할된 리스트 중 쓸모없는 부분을 버린다. 이를 재귀적으로 반복하여 전체 리스트에서 k번째로 작은(혹은 큰) 요소를 찾게된다

피봇 선택 -> 리스트 분할 -> 결과가 있는 리스트 재귀호출을 통해 값을 찾는다

특징

피봇이 리스트를 균등하게 나눴을때가 Good 분할, 한 쪽에 치우쳐지게 나눴을때가 Bad 분할이라고 할 때 평균 2회 연속 피봇을 랜덤으로 정하면 Good 분할을 할 수 있다. Good 분할만 했을 때 리스트 크기가 n에서부터 3/4배로 연속적으로 감소되고, 리스트 크기가 1일 때에는 더 이상 분할할 수 없게 되므로 평균적으로 O[n + 3/4n + (3/4)2n +(3/4)3n +… +(3/4)i-1n +(3/4)in] = O(n) -> O(n) x 2 = O(n)의 시간복잡도를 가지게 된다.

평균적으로 O(n)의 시간 복잡도를 가지기 때문에 정렬 알고리즘보다 빠른 속도를 가지고 있다.

구현

void swap(int *a, int *b)
{
	int tmp =*a;
	*a =*b;
	*b = tmp;
}

int randomPivot(int left, int right)
{
	int pivot;
	pivot = rand() % (right-left) + left;
	return pivot;
}

int selection(int a[], int left, int right, int k)
{
	int p, i, j, s;
	
	//무한루프 방지 
	if(left>=right) return a[left];
	
	//피봇선택 
	p = randomPivot(left, right);
	 
	i = left+1, j = right;
	
	//피봇과 left 위치 변경
	swap(&a[left], &a[p]);
	
	//피봇 앞 뒤 위치 정렬 
	while(i<=j)
	{
		if(a[i] > a[left])
		{
			if(a[j] < a[left])
			{
				swap(&a[i++], &a[j--]);
			}	
			else
			{
				j--;
			}
				
		}
		else
		{
			i++;
		}
	}
	swap(&a[left], &a[j]);
	
	s = (j-1)-left+1;
	 
	if(k<=s) selection(a, left, j-1, k); //피봇보다 작을 경우 
	else if(k == s+1) return a[j]; //찾은경우 
	else selection(a, j+1, right, k-s-1); //피봇보다 클 경우 
}