[알고리즘] 선택 알고리즘

선택 알고리즘은 n번째로 작은(or 큰)원소를 찾는 알고리즘이다.

선택 알고리즘은 동작 방식이 퀵정렬 알고리즘과 비슷하다.

1. 제일 우측값을 pivot으로 정하고 pivot보다 큰 값, 작은 값의 배열을 하나 만든다.

2. pivot값을 그 가운데에 대입한다.(이로써 pivot의 Index를 알 수 있다.)

3. n과 pivot의 Index를 비교해서 작으면 좌측 정렬에 크면 우측 정렬에 재귀적으로 실행한다.

4. 만약 pivot의 Index와 찾는 n이 같으면 리턴하고 종료

기존의 퀵정렬에서는 우축 좌측을 결과적으로 정렬하고 리턴 받아야하기 때문에 T(n) = 2T(n/2) + cn이였지만 선택 알고리즘에서는 찾는 값의 위치가 중요하기 때문에 지속적으로 더 작은 배열을 호출하기 때문에 성능면에서 더 좋은 퍼포먼스를 기대할 수 있다.

하지만 만약 최악의 케이스 즉 찾는 값이 지속적으로 큰 그룹에 속한다면 성능 보장이 어렵다. 이를 식으로 표현하면

T(n) = T(9n/10) + Θ(n)이다.

select(alist,p, r, n):
	if(len(alist) == 1): return alist[n]
    
    alist, q = partition(alist)
    k = p - q + 1
    
    if(i < k): return select(A, p, q - 1, n)
    else if(i == p): return return alist[q]
    else: return select(alist, q + 1, r, n - k)

선택 알고리즘의 실행 시간은 평균 Θ(n), 최악의 경우 Θ(n**2)이다.

n개의 원소들에 대해, 기준 원소가 k번째로 작은 원소이며, 두 부분 배열은 각각 k - 1개의 원소와 n - k개의 원소로 구성되어 있다.

이 때 실행시간 T(n)을 표현하면

T(n) <= max[T(k - 1), T(n - k)] + Θ(n)이다.

max는 더 큰값을 선택한다는 의미이다.

Θ(n)은 partition함수 같은 오버해드 비용이다.