선택 알고리즘 파이썬 구현

선택 알고리즘

이전 게시물 퀵 정렬 분할 알고리즘을 기본으로 함.

2021.07.29 - [알고리즘] - 퀵 정렬, 분할 알고리즘

 

퀵 정렬의 수행시간

분할 후 자기호출 -> 최악의 경우 O(N^2) 시간 소요

 

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

- 분할을 이용

- 평균 O(N), 최악의 경우 O(N^2) 시간 소요

 

분할 알고리즘이 리턴하는 값으로 기준원소가 전체에서 몇 번째 작은 원소인지 알 수 있다.

퀵 정렬을 필요한 부분만 해나가는 느낌

 

#평균 선형 시간 선택 알고리즘 select

def select(a, p, r, i):
    if p==r:
        return a[p]
    
    q = partition(a, p, r)
    k = q-p+1
    
    if i<k:
        return select(a, p, q-1, i)
    elif i==k:
        return a[q]
    else:
        return select(a, q+1, r, i-k)
    
def partition(a, p, r):
    pivot = a[r]
    i = p-1
    for j in range(p, r):
        if a[j] <= pivot:
            i += 1
            a[i], a[j] = a[j], a[i]
    
    a[r], a[i+1] = a[i+1], a[r]
    
    return i+1

arr = [5, 3, 1, 6, 2, 4]
print(select(a, 0, len(arr)-1, 2))

 

최악의 경우에도 선형 시간을 보장하는 선택 알고리즘

- 분할의 균형이 일정 비율 이상으로 나빠지지 않도록 전처리

- 최악의 경우 수행시간이 O(N)

 

 

 

 

참고 | 쉽게 배우는 알고리즘