Selection Problem, 중앙값과 순서통계량

i 번째 순서통계량이란 n개의 원소집합 중 i번째로 작은 원소를 말한다. 

 

논의를 간단하게 하기 위해 배열의 원소 개수가 짝수일 경우 (n+1)/2의 floor를 중앙값으로 간주하겠다.

또한, 모든 배열의 원소들이 서로 다른 집합을 가정한다. 그러나 같은 값을 포함하는 집합으로의 확장 역시 가능할 것이다.

 

선택문제는 정렬을 사용하면 O(n log n)의 시간에 풀 수 있다. 

그러나 정렬하지 않고 선택만을 할 경우 O(n)시간에 풀 수도 있다. 

 

1. 최소값과 최대값

모두가 짐작할 수 있는 가장 간단한 방법은 처음부터 끝까지 탐색을 하며 최대/최소값을 찾는 것이다. 

이는 n-1번의 비교가 필요하며, 이 이하로 적게 비교는 불가능하다. 

minimum(A)
    min=A[1]
    for i=2 to A.length
        if A[i]<min
            min=A[i]
    return min

 

최소값과 최대값을 동시에 구하는 것은 어떨까?

위의 알고리즘에 최대값을 구하는 과정을 추가하여 2(n-1)의 비교로 가능하다. 

 

그러나, 보다 짧은 3*(n/2)번의 비교만으로 최소값과 최대값을 동시에 구하는 방법이 존재한다.

이는 원소 각각을 현재의 최대값,최소값과 비교해서 원소당 두 번의 비교를 하는 대신 원소를 쌍으로 처리하는 것이다. 

두 개의 원소를 먼저 비교한 후, 큰 값을 최대값과, 작은 값을 최소값과 비교해나가는 것이다. 

이렇게 하면 원소 두 개당 세 번의 비교로 충분하다.

 

2. i 번째 순서통계량 선택하기

일반적인 선택 문제는 최소값을 찾는 문제보다 복잡해 보인다. 

그러나 놀랍게도 두 문제의 점근적인 수행시간은 O(n)으로 같다. 

 

quick sort 알고리즘을 기반으로 하지만, 양 쪽 모두를 재귀 처리하는 퀵정렬과는 달리 순서통계량을 선택하는 알고리즘은 한 쪽만 재귀처리한다. 

양쪽이 아닌 한쪽을 처리하는 것만으로도 수행시간이 O(n log n)에서 O(n)으로 감소한다. 

(quick sort에서와 마찬가지로 배열의 모든 원소들이 다를 경우를 가정한다. 중복되는 원소들이 있는 경우, quick_sort_for_same_element를 참고하면 될 것이다)

 

randomize_select(A,first,last,i)	//i번째로 작은 원소 구하기
    if first==last
        return A[first]
    mid=randomize_partition(A,first,last)
    k=mid-first+1
    if i==k							//기준 원소가 i번째로 작은 경우!
        return A[q]
    else if i<k
        return randomize_select(A,first,mid-1,i)
    else 
        return randomize_select(A,mid+1,last,i-k)

randomize_partition(A,first,last)
    r=random(first to last)
    SWAP(A[r],A[last]
    
    x=A[last]
    i=first-1
    for j=first to last-1
        if A[j]<x
            i++
            SWAP(A[i],A[j])
	i++
    SWAP(A[i],A[last])
    return i

 

물론 randomize_selection은 quick_sort와 같이 최악의 경우 수행시간이 O(n^2)이지만 평균적으로 선형시간 내에 동작하고 랜덤화되어있기 때문에 특정 입력때문에 최악의 케이스로 작동하는 일도 없다. 

 

수행시간에 대한 자세한 분석은 Intorduction to algorithms third edition 218p참조