선택 알고리즘

기본적인 내용은 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 알고리즘(코드)은 quickselect보다 느렸다.
- statistics 모듈에는 median 함수가 있는데, 여기에서 조차도 그냥 sort를 사용한다 (코드)
- LeetCode에는 이 알고리즘을 요구하는 Kth Largest Element in an Array 문제가 있는데, 여기에서도 sort를 사용한 코드들이 가장 빠르다.
- BOJ에도 이 알고리즘을 요구하는 K번째 수 문제가 있다. 역시 순위권에 있는 것은 소팅을 이용한 코드들이다. n의 범위가 5,000,000까지라서, quickselect를 쓰는 편이 좀더 빨라질 수도 있긴 한데, 그렇다고 가장 빠른 quickselect 구현으로 제출하면 메모리 초과가 난다.

선택 알고리즘

관련 문제