[[분류:알고리즘]] == 개요 == 선택 알고리즘(Selection Algorithm)은 정렬되지 않은 리스트에서 k번째로 작은(또는 큰) 원소를 찾는 알고리즘이다. 리스트 전체를 정렬하면 [math(\Theta(n \log n))]이 걸리지만, 이 알고리즘들을 이용하면 평균적으로 [math(\Theta(n))] 내에 해결이 가능하다. == 퀵 선택(Quick Select) == 퀵 정렬의 분할(Partition) 로직을 활용하여 탐색 범위를 좁혀나가는 방식이다. === 작동 단계 === 리스트에서 하나의 피벗(Pivot)을 선택한다. 피벗보다 작은 원소는 왼쪽, 큰 원소는 오른쪽으로 보낸다(Partition). 피벗이 놓인 위치가 찾고자 하는 k번째라면 해당 값을 반환한다. k가 피벗의 위치보다 작으면 왼쪽 구역만, 크면 오른쪽 구역만 선택하여 위 과정을 재귀적으로 반복한다. === 의사 코드 === {{{#!syntax java quickSelect(A[], p, r, k): if (p == r) return A[p] q ← partition(A, p, r) i ← q - p + 1 if (k == i) return A[q] else if (k < i) return quickSelect(A, p, q - 1, k) else return quickSelect(A, q + 1, r, k - i) }}} == 선형 시간 선택(Linear Time Selection) == 퀵 선택의 최악의 경우([math(\Theta(n^2))])를 해결하기 위해 '중앙값들의 중앙값'을 피벗으로 사용하는 방식이다. === 작동 단계 === 그룹화: 원소들을 5개씩 묶어 그룹을 만든다. 각 그룹의 중앙값: 각 5개짜리 그룹 내에서 중앙값을 찾는다. 중앙값들의 중앙값(M): 단계 2에서 구한 중앙값들을 모아 다시 그들의 중앙값 M을 찾는다. 분할: M을 피벗으로 삼아 전체 리스트를 분할한다. 재귀: 분할된 위치에 따라 k번째 원소가 있는 구역으로 이동하여 과정을 반복한다. === 의사 코드 === {{{#!syntax java linearTimeSelect(A[], p, r, k): if (r - p + 1 <= 5) A[p...r]을 정렬하여 k번째 원소를 반환한다. // 그룹별 중앙값 구하기 for i ← 0 to ⌈(r - p + 1) / 5⌉ - 1 B[i] ← 5개 원소 그룹 중 중앙값 // 중앙값들의 중앙값 M 구하기 M ← linearTimeSelect(B, 0, ⌈(r - p + 1) / 5⌉ - 1, ⌈(r - p + 1) / 10⌉) q ← partitionWithPivot(A, p, r, M) i ← q - p + 1 if (k == i) return A[q] else if (k < i) return linearTimeSelect(A, p, q - 1, k) else return linearTimeSelect(A, q + 1, r, k - i) }}} == 성능 분석 == 퀵 선택: 평균 [math(\Theta(n))], 최악 [math(\Theta(n^2))] 선형 시간 선택: 모든 경우 [math(\Theta(n))]
