====== 선택 알고리즘 ======
  * 기본적인 내용은 [[https://en.wikipedia.org/wiki/Selection_algorithm]] 을 참조
  * 이론적으로는
    * QuickSelect 를 쓰면 k번째 원소를 평균 O(n)에 구할 수 있다.
    * Median of median 을 쓰면 k번째 원소를 최악 O(n)에 구할 수 있다.
    * IntroSelect는 두가지를 적절히 섞은 알고리즘이다
  * 실질적으로는
    * Median of median은 구현이 복잡해서 상수값이 워낙 크다보니 거의 어디서도 안쓰인다..
    * cpp의 nth_element는 introselect를 쓴다
    * 그리고 **CPython에서는 정렬하고 k번째 원소를 리턴하는 것이 가장 효율적이다**
  * Python에서 sort를 쓰는 것이 낫다는 것에 대한 보충설명
    * 직접 간단히 테스트해본 결과 
      * 대충 100,000 이하의 n에 대해서는 sorted()로 소팅한 뒤 k번째 원소를 리턴하는 것이 QuickSelect를 구현해서 찾는 것보다 더 빨랐다.
      * 대략 n이 500,000을 넘어가면, 가장 빠르게 구현한 QuickSelect가 sorted보다 빨라졌지만 차이는 크지 않았다.
      * 구현에 관해서는 
        * 실행시간은 in-place 비재귀 버전 > in-place 재귀버전 > list를 계속 생성하는 재귀버전 순서였다. list를 계속 생성하는 재귀버전이 가장 빠르기는 한데 메모리가 너무 증가하는 문제가 있다..
        * floyd-rivest 알고리즘([[https://github.com/lycantropos/quickselect/blob/master/quickselect/floyd_rivest.py|코드]])은 quickselect보다 느렸다.
    * statistics 모듈에는 median 함수가 있는데, 여기에서 조차도 그냥 sort를 사용한다 ([[https://github.com/python/cpython/blob/3.9/Lib/statistics.py|코드]])
    * LeetCode에는 이 알고리즘을 요구하는 [[ps:problems:leetcode:215|Kth Largest Element in an Array]] 문제가 있는데, 여기에서도 sort를 사용한 코드들이 가장 빠르다.
    * BOJ에도 이 알고리즘을 요구하는 [[ps:problems:boj:11004|K번째 수]] 문제가 있다. 역시 순위권에 있는 것은 소팅을 이용한 코드들이다. n의 범위가 5,000,000까지라서, quickselect를 쓰는 편이 좀더 빨라질 수도 있긴 한데, 그렇다고 가장 빠른 quickselect 구현으로 제출하면 메모리 초과가 난다.

===== 관련 문제 =====
  * [LeetCode] [[ps:problems:leetcode:215|Kth Largest Element in an Array]] 
  * [BOJ] [[ps:problems:boj:11004|K번째 수]]