[알고리즘]11.선택 알고리즘
1. 평균 선형 시간 선택 알고리즘 (1) 기준 원소보다 작거나 같은 원소는 기준 원소의 왼쪽 그룹으로 재배치한다. (2) 기분 원소보다 큰 원소는 기준원소의 오른쪽으로 재배치한다. (3) 1,2의 과정에 의해 기준원소가 전체에서 몇 번째 작은 원소인지 알 수 있다. => 기준원소 = 전체에서 k번째 작은 원소 (4) i i 는 왼쪽 그룹에 있다. (5) i = k => 기준 원소 = i (6) i i는 오른쪽 그룹에 있다. select(A,p,r,i) //배열 A[p...r] 에서 i 번째 작은 원소를 찾는다. { if (p=r) then return A[p]; => 원소가 하나뿐일 경우 i는 반드시 1 q 기준원소 = i else return select (A,q+1,r,i-l);=> 오..