선택 알고리즘

목차

1. 개요
2. 퀵 선택(Quick Select)
2.1. 작동 단계
2.2. 의사 코드
3. 선형 시간 선택(Linear Time Selection)
3.1. 작동 단계
3.2. 의사 코드
4. 성능 분석

1. 개요 _{✎ ⊖}

선택 알고리즘(Selection Algorithm)은 정렬되지 않은 리스트에서 k번째로 작은(또는 큰) 원소를 찾는 알고리즘이다. 리스트 전체를 정렬하면 \Theta(n \log n)이 걸리지만, 이 알고리즘들을 이용하면 평균적으로 \Theta(n) 내에 해결이 가능하다.

2. 퀵 선택(Quick Select) _{✎ ⊖}

퀵 정렬의 분할(Partition) 로직을 활용하여 탐색 범위를 좁혀나가는 방식이다.

2.1. 작동 단계 _{✎ ⊖}

리스트에서 하나의 피벗(Pivot)을 선택한다.

피벗보다 작은 원소는 왼쪽, 큰 원소는 오른쪽으로 보낸다(Partition).

피벗이 놓인 위치가 찾고자 하는 k번째라면 해당 값을 반환한다.

k가 피벗의 위치보다 작으면 왼쪽 구역만, 크면 오른쪽 구역만 선택하여 위 과정을 재귀적으로 반복한다.

2.2. 의사 코드 _{✎ ⊖}

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)

3. 선형 시간 선택(Linear Time Selection) _{✎ ⊖}

퀵 선택의 최악의 경우(\Theta(n^2))를 해결하기 위해 '중앙값들의 중앙값'을 피벗으로 사용하는 방식이다.

3.1. 작동 단계 _{✎ ⊖}

그룹화: 원소들을 5개씩 묶어 그룹을 만든다.

각 그룹의 중앙값: 각 5개짜리 그룹 내에서 중앙값을 찾는다.

중앙값들의 중앙값(M): 단계 2에서 구한 중앙값들을 모아 다시 그들의 중앙값 M을 찾는다.

분할: M을 피벗으로 삼아 전체 리스트를 분할한다.

재귀: 분할된 위치에 따라 k번째 원소가 있는 구역으로 이동하여 과정을 반복한다.

3.2. 의사 코드 _{✎ ⊖}

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)

4. 성능 분석 _{✎ ⊖}

퀵 선택: 평균 \Theta(n), 최악 \Theta(n^2)

선형 시간 선택: 모든 경우 \Theta(n)

선택 알고리즘

1. 개요 ✎ ⊖

2. 퀵 선택(Quick Select) ✎ ⊖

2.1. 작동 단계 ✎ ⊖

2.2. 의사 코드 ✎ ⊖

3. 선형 시간 선택(Linear Time Selection) ✎ ⊖

3.1. 작동 단계 ✎ ⊖

3.2. 의사 코드 ✎ ⊖

4. 성능 분석 ✎ ⊖