선택 알고리즘

t1. 평균 선형 시간 선택 알고리즘

i번째 원소를 찾는 알고리즘은 앞에서 퀵소트의 파티션을 이용한다. 아래는 그 과정을 나타낸 그림이다.

파티션을 하면 기준원소가 몇번째에 있는지는 확실히 알 수 있다. 이를 이용해서 i번째 원소를 찾는 것이다. 이에 대한 알고리즘은 아래와 같다.

아래는 직접 구현해본 코드이다. 

def partition(A, p, r):
    standard = A[r]
    part_1 = p
    
    for part_3 in range(p, r):
        if A[part_3] <= standard:
            temp = A[part_1]
            A[part_1] = A[part_3]
            A[part_3] = temp
            part_1 += 1
    
    temp = A[r]
    A[r] = A[part_1]
    A[part_1] = temp
    
    return part_1

def select(A, p, r, i):
#select ith element in sorted array A[p,,,r]
    #if there's only one element in array A, then return that element
    if p == r:
        return A[p]
    
    q = partition(A, p, r)
    
    #k : kth element in sorted array A
    k = q-p+1
    
    #if k>i implement the function again until k=i
    if k > i:
        return select(A, p, q-1, i)
    
    #if k=i then return that element
    elif i == k:
        return A[q]
    
    #if k<i then implement the function again start with q+1,
    #we already found kth element so find (i-k)th element 
    else:
        return select(A, q+1, r, i-k)

이 알고리즘의 수행시간은 T(n)≤max[T(k-1), T(n-k)] + Θ(n)이다. max[T(k-1), T(n-k)]는 파티션이후 기준원소가 k번째이라는 것을 알았을 때 k<i이면 앞부분에서 다시 찾아야 함으로 T(k-1)이 걸리고, k>i이면 뒷부분에서 다시 찾아야 함으로 T(n-k)가 걸리게 된다. 그리고 상한선을 찾음으로 max를 이용해 둘중 나쁜 경우를 찾으면 된다. 또한 Θ(n)은 partition할때 걸리는 시간이다. 하지만 이것을 정리하면 T(n) = O(n)이라는 것이 나온다. 그 증명은 아래와 같다 .

위에서 T(n)=O(n)이고 하한선은 Ω(n)임으로 T(n) = Θ(n)이다. 그냥 정렬하고 선택을 하면 아무리 잘해도 Θ(nlogn)이나오는데 이 알고리즘대로라면 Θ(n)으로 시간을 줄 일 수 있는 것이다. 다만 최악의 경우는 조금 다른데 만약 partition이후가 계속 한쪽으로 몰린다면 시간 복잡도는 T(n) = T(n-1) + Θ(n)이 나와서 T(n) = Θ(n^2)이 나오게 된다. 또한 partition이후의 균형이 자주 깨져도  T(n) = Θ(n^2)가 나오게 된다. 

 

2. Medians of medians

이 알고리즘은 위에서 균형이 깨지는 경우를 어느정도 커버를 해준다. 알고리즘은 아래와 같다.

위에서 5번의 경우를 그림으로 나타내면 아래와 같다.

이렇게 중앙값의 중앙값을 찾은 다음 그 값을 partition의 standard element로 이용해 나머지 초록색을 제자리로 옮기는 방식이다. 이를 직접 구현한 코드는 아래와 같다. 

#sort the given list and return the position of median
def sort_and_get_median(data, start, end):
    data[start:end+1] = sorted(data[start:end+1])
    return (start+end)//2
##################################################################
def choose_pivot(data, start, end):
    if end-start<5:
        return sort_and_get_median(data, start, end)
    
    #find the median and move that in front of list
    cur = start
    for i in range(start, end+1, 5):
        median_loc = sort_and_get_median(data, i, min(i+4, end))
        data[cur] , data[median_loc] = data[median_loc], data[cur]
        cur += 1
    
    #now the median elements are placed from 0 to cur
    return quickselect_pos(data, start, cur-1, (cur+start-1)//2)
##################################################################
#return pivot position's right location
def partition(data, start, end, pivot_pos):
    data[end], data[pivot_pos] = data[pivot_pos], data[end]
    standard = data[end]
    part_1 = start
    
    for part_3 in range(start, end+1):
        if data[part_3]<standard:
            temp = data[part_1]
            data[part_1] = data[part_3]
            data[part_3] = temp
            part_1 += 1
            
    temp = data[part_1]
    data[part_1] = data[end]
    data[end] = temp
    
    return part_1
###################################################################
#return selected position not value
def quickselect_pos(data, start, end, k):
    if start == end:
      return start
    
    pivot = choose_pivot(data, start, end)
    partition_ = partition(data, start, end, pivot)
    
    if partition_ == k:
        return partition_
    elif partition_ > k:
        return quickselect_pos(data, start, partition_-1, k)
    elif partition_ < k:
        return quickselect_pos(data, partition_+1, end, k)
##################################################################   
#return selected kth value of the list
def quickselect(data, start, end, k):
    if start == end:
        return data[start]
    
    pivot = choose_pivot(data, start, end)
    
    partition_ = partition(data, start, end, pivot)

    if partition_ == k:
        return data[partition_]
    elif partition_ > k:
        return quickselect(data, start, partition_-1, k)
    elif partition_ < k:
        return quickselect(data, partition_+1, end, k)
    

이 알고리즘의 최악의 경우를 생각하면 다음과 같다. 중간값의 중간값(M)을 구한다음 partition을 이용하여 그 중간값의 위치를 얻으려고 한다. 어차피 파란색과 빨간색 동그라미는 위치가 정해져있지만 초록색이 정확한 위치가 안정해져 M의 오른쪽 또는 왼쪽으로 이동하는데 이때 모든 초록색이 M의 한쪽(여기서 왼쪽이라하자)으로 이동하는 경우이다. 이런 경우에 M보다 큰 원소는 아래의 이유로 이다. 

그렇다면 나머지 M보다 작은 원소는 전체 n에서 을 뺀 이다. 그러므로 최악의 경우에도 의 비율을 유지하는 것이다. 이렇게 비율이 유지되면 선형시간 알고리즘이 된다.

각 단계의 시간 복잡도를 살펴보자. 1단계에서는 Θ(1)이다. 2단계에서는 5개의 그룹으로 묶는데 n개의 원소를 돌면서 함으로 Θ(n)이다. 3단계에서는 n/5개의 그룹을 돌면서 중앙값을 찾음으로 Θ(n)이고 5단계는 partition임으로 Θ(n)이다. 4단계와 6단계는 자기 호출인데 4단계는 n/5개의 그룹을 가지고 selection함으로 T(n/5)이고 6단계는 적합한쪽이 최악의 경우라고 생각하면 T(7n/10+2)이다. 그러므로 시간복잡도는 아래와 같이 나타낼 수 있다.

이에 대한 증명은 아래와 같다.

따라서 이방법으로 최악의 경우에도 Θ(n)을 유지할 수 있다.