Quick Selection을 이용한 k번째 숫자 탐색: O(n)의 시간 복잡도

N개의 원소 중 k번째로 작은 수를 찾아라 라는 문제를 만났을 때 가장 많이 사용하는 방법 중 하나는 컨테이너를 sorting 후에 k번째 인덱스를 참조하는 방식을 사용한다.

 

하지만 이렇게 정렬을 했을 경우엔 전체 시간 복잡도가 worst case O(N^2) 혹은 O(N longN)가 되어버리므로 원소의 개수가 많을 경우엔 적합하지 않다. 따라서 Quick Selection 알고리즘을 이용해서 O(N)의 시간 복잡도를 가지는 탐색을 구현할 수 있다.

 

이름에서도 유추할 수 있듯이 기본 idea는 Quick Sort에서 따왔다.

 

int quick_selection(int n, int* ArrList, int k)
{
	if (ArrList == NULL || n <= k) return -1;

	int start = 0;
	int end = n - 1;

	while (start < end)
	{
		int i = start;
		int j = end;
		int mid = ArrList[(i + j) / 2];

		while (i < j)
		{
			if (ArrList[i] >= mid)
			{
				std::swap(ArrList[i], ArrList[j]);
				j--; // j번째 인덱스는 pivot 보다 큰 값이 확실해졌으니 -1 해준다!
			}
			else i++; // i번재 인덱스는 pivot 보다 작은 값이 확실해졌으니 +1 해준다!
		}

		if (ArrList[i] > mid) i--;	// ArrList[i]>mid 라면 i-1번째까지
						// ArrList[i]<=mid 라면 i번재까지
						// pivot보다 작은 값임을 확신할 수 있다!
		if (k <= i) end = i;
		else start = i + 1;
        // k가 포함된 부분을 가지고 다시 selection을 진행한다.(분할 정복 과정)
	}
	return ArrList[k];
}

 

+[C++] STL nth_element

이걸 자동으로 구현해주는 STL이 있다.. 바로바로 nth_element

사용방법은 std::nth_element(arr, K, arr+N, (pred))와 같다. (pred를 통해 정렬 순서 지정)