선택 문제 알고리즘

선택(Selection) 문제는 n개의 숫자들 중에서 k 번째로 작 은 숫자를 찾는 문제 

“1000개의 숫자가 랜덤하게 존재하는 배열 A가 있다. 이 배열에서 300번째 작은 수는 얼마인가?”

 

이진탐색은 정렬된 입력의 중간에 있는 숫자와 찾고자 하 는 숫자를 비교함으로써, 입력을 1/2로 나눈 두 부분 중 에서 한 부분만을 검색

• 선택 문제는 입력이 정렬되어 있지 않으므로, 입력 숫자 들 중에서 (퀵 정렬에서와 같이) 피봇을 선택하여 아래와 같이 분할

Selection(A, left, right, k) 입력: A[left]~A[right]와 k, 단, 1≤k≤|A|, |A|=right-left+1 출력: A[left]~A[right]에서 k 번째 작은 원소

 

선택 알고리즘은 데이터 분석을 위한 중앙값 (median) 을 찾는데 활용된다.