[Algorithm] quick select

quick select는 배열에서 정렬되었을 경우의 N번째 요소를 가져오는 알고리즘이다.
quick sort와 동일한 pivot 기반의 알고리즘이다.

quick sort를 안다면 이것도 쉽게 이해할 수 있을 것이다. quick sort에서 정렬을 그냥 하다 마는 것이기 때문이다.

평균 복잡도가 O(n)이라서, 딱 그거만 찾으면 되는 경우엔 O(nlog2n)인 정렬 알고리즘을 쓰는것보다 훨씬 빠르다.
다만 quick sort처럼 엣지 케이스에는 O(N^2)의 성능이 나올 수도 있다. 물론 매우 드물다.

근데 이걸 실무에서 쓸일이 있나...? 나는 못본거같다.
나라면 N번째 요소를 찾을 일이 잦으면 그냥 트리나 sorted array 같은걸 쓸 것 같다.

코테용인듯

원리

기본적인 원리는 quick sort의 동작방식과 유사하다.
분할 정복(Divide and Conquer)이라고도 한다.

1. 먼저 배열 목록에서 피벗을 하나 고른다. (아무거나 상관없다.)
2. 배열을 쭉 돌면서 피벗을 기준으로 해서 작은걸 왼쪽에, 큰걸 오른쪽에 모아놓고 피벗을 그 중간에 둔다.
3. 그러면 양쪽은 몰라도 피벗 딱 하나에 대해서는 정렬시 위치를 찾은 것이다.
4. 그래서 피벗의 인덱스와 찾는 값 n이 같다면 결과는 찾은 셈이다.
5. 같지 않다면 피벗을 기준으로 해서 왼쪽 배열이나 오른쪽 배열을 가지고 다시 재귀 로직을 수행한다... 1번부터 다시 반복하는 것이다. 다만 quick sort와 다르게 모든걸 정렬할 필요는 없으므로, 대소비교로 필요한 방향으로만 들어가면 된다.

유의할 점은, pivot에서 계속 최대값이나 최소값을 찝으면 최악의 성능으로 O(N^2)이 나올 수 있다는 것이다. 중간 정도 크기의 값이 잡혀야 최선의 성능이 나온다.

구현

예시 코드는 자바스크립트다.

피벗을 만들고 그 양쪽을 정렬해주는 partition 함수와, 그걸 호출해서 분할 처리를 하는 재귀함수 quick_select로 나누어 구현했다.

function partition(list, left, right) {
	let pivot = left; // 왼쪽부터 탐색

	for (let i = left; i < right; i++) {
		if (list[i] < list[right]) {
			// swap
			const temp = list[i];
			list[i] = list[pivot];
			list[pivot] = temp;

			pivot += 1;
		}
	}

	// swap
	const temp = list[pivot];
	list[pivot] = list[right];
	list[right] = temp;

	return pivot;
}

function quick_select(list, left, right, n) {
	if (left == right) {
		return list[left];
	}

	const pivot = partition(list, left, right);

	if (n == pivot) {
		return list[n];
	} else if (n < pivot) {
		return quick_select(list, left, pivot - 1, n);
	} else {
		return quick_select(list, pivot + 1, right, n);
	}
}

그리고 돌려보겠다.
다음과 같은 배열이 있고 인덱스 기준 2번째를 찾는다면

[1,2,3,4,5]이므로 3이 나와야 한다.

잘 나온다.

참조
https://ko.m.wikipedia.org/wiki/%ED%80%B5%EC%85%80%EB%A0%89%ED%8A%B8
https://www.daleseo.com/quick-select/