Quicksort(2) : Selection

Selection

이번에는 '선택'과 관련한 문제입니다.

• 만약 어떤 배열에서 '최소/최대'의 값을 구해야 한다면 배열을 한 번만 쭉 훑으면서 최소/최대의 값을 저장하면 되기 때문에 선형 시간이 필요할 것입니다.
  즉, N만큼의 시간이 소요되죠.

• 하지만 배열에서 k번째의 값을 구하려면 이는 단순히 한 번 훑어보는 것으로 판단할 수 있는 문제가 아니게 됩니다.
  정렬 후 k번째 값을 가져오면 되지만 이는 linearithmic, 즉 NlogN만큼의 시간이 필요한 작업입니다.
  뭔가 비슷한듯 비슷하지 않은 두 방식에 대해서, 후자도 선형 시간으로 처리할 수 있지 않을까? 라는게 과거 학자들의 궁금증이었습니다.

 

 

Quick-select

import random

def partition(a, lo, hi):
    i, j = lo, hi+1
    while True:
        i += 1
        while i < hi and less(a[i], a[lo]):
            i += 1

        j -= 1
        while j > lo and less(a[lo], a[j]):
            j -= 1

        if i >= j:
            break

        exch(a, i, j)

    exch(a, lo, j)
    return j

def quickselect(a, k):
    random.shuffle(a)
    lo, hi = 0, len(a)-1
    while hi > lo:
        j = partition(a, lo, hi)
        if j < k:
            lo = j + 1
        elif j > k:
            hi = j - 1
        else:
            return a[k]
    return a[k]

별다른 장치 없이 파이썬 코드로 변환하면 위와 같습니다.

이때 less라는 내장 함수는 파이썬에 없으므로 비교 연산자로 바꿔줘야 합니다.

• partition을 나누어 두 요소를 재귀적으로 비교하는 과정이 퀵 정렬과 완전히 동일합니다.
• 하지만 찾고자하는 k가 등장하면 반복문을 종료하며 값을 반환하는 점에서 차이가 있습니다.

 

 

Quick-select: mathematical analysis

이 방식도 퀵 정렬에서와 마찬가지로, 배열이 이미 정렬되어 있는 경우 quadratic(이차) 시간 복잡도를 갖습니다.

따라서 이런 문제를 사전 방지하기 위해 배열을 무작위로 섞는 작업이 필요합니다.

 

 

Theoretical context for selection

 

 

 

출처: Coursera, Algorithms, Part 1, Princeton University