[자료구조] 퀵 셀렉트

무작위로 정렬된 배열이 있을 때, 정렬은 안 해도 되지만 배열에서 열 번째로 작은 값 혹은 열다섯 번째로 큰 값을 알고 싶다고 하자. 가령 수많은 시험 점수가 있을 때 25번째 백분위수나 중간 점수를 알고 싶을 때 도움이 될 것이다. 전체 배열을 정렬한 후 적절한 셀을 바로 찾아보면 확실히 문제를 해결할 수 있지만 퀵 셀렉트라고 알려진 뛰어난 작은 알고리즘으로 훨씬 더 나은 성능을 낼 수 있다. 퀵 셀렉트도 퀵 정렬처럼 분할에 기반하며, 퀵 정렬과 이진 검색의 하이브리드 정도로 생각할 수 있다.

 

값이 8개인 배열이 있을 때 이 배열 내에서 두 번째로 작은 값을 찾고 싶다고 하자. 먼저 전체 배열을 분할한다.

분할 후 피벗은 배열의 중간 부분에 있을 것이다.

이제 피벗은 올바른 위치며, 다섯 번째 셀이므로 어떤 값이 배열 내에서 다섯 번째로 작은지 알게 됐다. 두 번째로 작은 값은 피벗의 왼쪽 어딘가에 있다는 것도 안다. 이제 피벗 오른쪽에 있는 모든 수는 무시한다. 퀵 정렬과 유사하지만 퀵 셀렉트는 나눠진 반쪽에만 집중한다.

이제 피벗 왼쪽에 있는 하위 배열을 분할한다. 새 피벗은 세 번째 셀로 하자.

이제 세 번째 셀의 값이 올바른 위치에 있게 됐고, 이 값이 배열에서 세 번째로 작은 값임을 안다. 두 번째 작은 값을 구하기 위해 또 한 번 왼쪽에 있는 하위 배열을 분할하자.

분할이 끝나면 가장 작은 값과 두 번째로 작은 값이 배열 내에서 올바른 위치에 있게 된다. 이제 이 값을 가져와 사용할 수 있다. 퀵 셀렉트의 훌륭한 점 중 하나는 전체 배열을 정렬하지 않고도 올바른 값을 찾을 수 있다는 것이다.

#include <vector>
#include <iostream>
using namespace std;

class CSortArray
{
public:
	CSortArray() = default;
	CSortArray(vector<int>& arr)
	{
		array = arr;
	}

	int partition(int lptr, int rptr)
	{
		int pivot_pos = rptr;
		int pivot = array[pivot_pos];
		rptr--;

		while (true)
		{
			while (array[lptr] < pivot)
				lptr++;
			while (array[rptr] > pivot)
				rptr--;

			if (lptr >= rptr)
				break;
			else
				swap(lptr, rptr);
		}

		swap(lptr, pivot_pos);
		return lptr;
	}

	void swap(int ptr1, int ptr2)
	{
		int tmp_value = array[ptr1];
		array[ptr1] = array[ptr2];
		array[ptr2] = tmp_value;
	}

	vector<int> array;
};

class CQuickSelection : public CSortArray
{
public:
	CQuickSelection() = default;
	CQuickSelection(vector<int>& arr) : CSortArray(arr) {};

	int quickselection(int lowest_value, int leftIndex, int rightIndex)
	{
		if (rightIndex - leftIndex <= 0)
			return array[leftIndex];

		int pivot_pos = partition(leftIndex, rightIndex);

		if (lowest_value < pivot_pos)
			return quickselection(lowest_value, leftIndex, pivot_pos - 1);
		else if (lowest_value > pivot_pos)
			return quickselection(lowest_value, pivot_pos + 1, rightIndex);
		
		return array[pivot_pos];
	}
};

int main()
{
	vector<int> testArr = { 0, 50, 20, 10, 60, 30 };
	CQuickSelection quickSort(testArr);
	int n = quickSort.quickselection(3, 0, testArr.size() - 1);

	cout << n << endl;
	return 0;
}

index는 0부터 시작하므로 4번째를 찾으려고 3을 기입했다. 결과는 4번째 값인 30이 출력되었다.