k-th smallest selection algorithm (k번째로 작은 숫자를 찾는 알고리즘)

http://hackability.kr/entry/Quick-Selection%EC%9D%84-%EC%9D%B4%EC%9A%A9%ED%95%9C-On-%EC%84%A0%ED%83%9D-%EB%B0%A9%EB%B2%95

보통 배열안에서 k번째로 작은 숫자를 구하라라고 하면

sort 한 후에 arr[k] 이런식으로 찾는데

O[nlogn]의 매우 비효율적인 방법이다.

worst case가 O[n]의 방법을 소개한다.