"n개의 숫자들 중 k번째로 작은 숫자 찾기"
최소 숫자를 k번 찾음 -> 찾은 뒤에는 입력에서 제거
- 피봇보다 작은 수는 피봇의 좌측(Small group), 피봇보다 큰 수는 피봇의 우측(Large group)으로 배열 정렬
- 그 좌측 우측에다 재귀적으로 1번을 적용한다.
이때 알아야 할 것은 "각 그룹의 크기" 즉, 숫자의 개수
각 그룹의 크기를 알면, "k번째 작은 숫자가 어느 그룹에 있는지", "그 그룹에서 몇 번째로 작은 숫자를 찾아야하는지"를 알 수 있다.
예컨대 다음 예제를 살펴보자.
<pivot index = 2 ----> large group에서 재귀>
<pivot index = 7 ----> large group에서 재귀>
Selection(A, left, right, k)
입력: A[left]~A[right]와 k, 단, 1<=k<=|A|, |A|=right-left+1
출력: A[left]~A[right]에서 k번째 작은 원소
1. 피봇을 A[left]~A[right]에선 랜덤하게 선택하고, 피봇과 A[left]의 자리를 바꾼 후,
피봇과 배열의 각 원소를 비교하여 피봇보다 작은 숫자는 A[left]~A[p-1]로 옮기고
피봇보다 큰 숫자는 A[p+1]~A[right]로 옮기며, 피봇은 A[p]에 놓는다.
2. S=(p-1)-left+1 //S = Small group의 크기 -> k번째 숫자가 어느 그룹에 있는지 파악 & 그 그룹에서 몇 번째로 작은 숫자를 찾아야 하는지 파악
3. if(k<=S) Selection(A, left, p-1, k)
4. else if(k = S+1) return A[p] //피봇 = k번째 작은 숫자
5. else Selection(A, p+1, right, k-S-1) //large group에서 찾기