8. Sorting in Linear Time

지금까지 본 \Omega(n \lg n)의 정렬 알고리즘은 입력 원소간의 비교에 수행 시간이 의존하는 비교 정렬이었다. 비교 정렬은 그보다 더 빠르기가 불가능하지만, 다른 방법의 정렬은 더 빠를 수도 있다.

8.1. Lower bounds for sorting

비교 정렬은 결정 트리로 추상화할 수 있다. 결정 트리는 특정한 입력에 대해 해당 입력 내의 원소들간 비교를 표현하는 전 이진 트리이다. 트리의 리프 노드 각각은 입력의 순열이 된다. 모든 정렬 알고리즘은 모든 순열을 출력할 수 있어야 하기 때문에, 이 리프 노드들은 트리의 루트에서부터 도달 가능해야 한다. 그러므로 트리로부터 리프까지의 거리가 수행 시간의 하한이 된다. 트리에는 n!개의 리프가 있으므로 하한은 \lg (n!) = \Omega(n \lg n)이다.

Theorem. 모든 비교 정렬 알고리즘의 수행시간은 \Omega(n \lg n)의 하한을 갖는다.

Theorem. 힙 정렬과 병합 정렬은 점근적으로 최적인 비교 정렬이다.

8.2. Counting sort

셈 정렬은 n개의 원소가 구간 [0, k]에 존재한다고 가정한다. k = O(n)이면 이 정렬은 \Theta(n)이 된다. 셈 정렬은 각각 원소에 대해 그 원소보다 작은 원소의 개수를 판단한 뒤 원소에 알맞는 위치에 직접 배치시키며, 원소의 값이 일부 같은 경우도 처리한다.

COUNTING-SORT(A, B, k)
let C[0, ..., k] be a new array
for i = 0 to k
    C[i] = 0
for j = 1 to A.length
    C[A[j]] = A[j] + 1
// now C[i] = # of elems equal to i
for i = 1 to k
    C[i] = C[i] + C[i - 1]
// now C[i] = # of elems <= i
for j = A.length downto 1
    B[C[A[j]]] = A[j]
    C[A[j]] = C[A[j]] - 1

셈 정렬의 수행 시간은 \Theta(k + n)인데, 셈 정렬은 주로 k = O(n)일 때 쓰므로 이 경우 \Theta(n)이 된다. 셈 정렬은 원소간 비교를 하지 않으며 안정된 알고리즘이다. 즉, 같은 원소들간 순서가 보존된다. 이 성질은 기수 정렬의 서브루틴으로서 셈 정렬이 사용될 때 중요하다.

8.3. Radix sort

기수 정렬은 가장 뒷쪽 자리수부터 자리수 내의 숫자들에 따라 입력을 정렬하는 알고리즘이다.

RADIX-SORT(A, d)
for i = 1 to d
    use a stable sort to sort array A on digit i

Lemma. 안정적 정렬(셈 정렬)이 \Theta(n + k) 시간이 걸린다면, k개의 값을 가질 수 있는 d자리 수들 n개에 대한 기수 정렬은 \Theta(d(n+k)) 시간이 걸린다.

Lemma. 안정적 정렬(셈 정렬)이 \Theta(n + k) 시간이 걸릴 경우 k개의 값을 가질 수 있는 n개의 비트 숫자에 대해 r \leq b라면 기수 정렬은 \Theta((b / r)(n + 2^{r}) 시간이 걸린다.

이 때 r의 적절한 값은 b에 따라 달라진다. b < \lfloor \lg n \rfloor이면 모든 r \leq b에 대해 \Theta(n)이 된다. b \geq \lfloor \lg n \rfloor이면 r = \lfloor \lg n \rfloor가 최적이며, 이 때는 \Theta(bn/ \lg n)이다.

기수 정렬은 서브루틴으로 셈 정렬을 사용할 경우 제자리 정렬이 아니기 때문에 퀵 정렬에 비해 단점을 갖는다. 또한 \Theta(n)의 시간을 갖는다고 해도 비례상수가 클 수 있으며, 퀵 정렬의 경우 캐시 활용을 더 잘 한다는 장점도 있다.

8.4. Bucket sort

버킷 정렬은 입력이 균등분포에서 독립적으로 샘플된다고 가정하며 평균 O(n)의 수행시간을 가진다. 일반성을 잃지 않고 분포 구간을 [0, 1)이라 하면 버킷 정렬은 이를 n개의 버킷으로 n등분하여 n개의 입력을 버킷들로 분배한다. 이후 버킷 내의 숫자들을 정렬한 뒤 버킷들 내의 원소들을 버킷 순서대로 늘어놓는다.

BUCKET-SORT(A)
let B[0, ..., n-1] be a new array
n = A.length
for i = 0 to n - 1
    make B[i] an empty list
for i = 1 to n
    insert A[i] into list B[floor(nA[i])]
for i = 0 to n - 1
    sort list B[i] with insertion sort
concatenate the lists B[0], ..., B[n-1] together in order

수행 시간은 n_{i}가 버킷 B[i]에 들어간 원소의 개수일 때 T(n) = \Theta(n) + \sum_{i=0}^{n-1} O(n_{i}^{2})이 된다. 이 정렬의 기대 시간은 \mathbb{E}[T(n)] = \Theta(n) + \sum_{i=0}^{n-1} O(\mathbb{E}[n_{i}^{2}])인데, X_{ij}를 A[j]가 버킷 i에 속하는 사건의 지시확률변수라 하면 n_{i} = \sum_{j=1}^{n} X_{ij}이므로

\mathbb{E}[n_{i}^{2}] = \mathbb{E}[(\sum_{j=1}^{n} X_{ij})^{2}] = \mathbb{E}[\sum_{j=1}^{n} X_{ij}^{2} + \sum_{1 \leq j \leq n}\sum_{1 \leq k \leq n, k \neq j} X_{ij}X_{ik}] = \sum_{i=1}^{n} \mathbb{E}[X_{ij}^{2}] + \sum_{1 \leq j \leq n}\sum_{1 \leq k \leq n, k \neq j} \mathbb{E}[X_{ij}X_{ik}]이 된다.

그런데 \mathbb{E}[X_{ij}^{2}] = 1^{2} \cdot \frac{1}{n} + 0^{2} \cdot (1 - \frac{1}{n}) = \frac{1}{n}이고, k \neq j이면 \mathbb{E}[X_{ij}X_{ik}] = \mathbb{E}[X_{ij}]\mathbb{E}[X_{ik}] = \frac{1}{n} \frac{1}{n} = \frac{1}{n^{2}}이므로 \mathbb{E}[n_{i}^{2}] = \sum_{j=1}^{n} \frac{1}{n} + \sum_{1 \leq j \leq n}\sum_{1 \leq k \leq n, k \neq j} \frac{1}{n^{2}} = 2 - \frac{1}{n}이 된다. 그러므로 \mathbb{E}[T(n)] = \Theta(n) + n \cdot O(2 - \frac{1}{n}) = \Theta(n)이 된다.

꼭 입력이 균등분포에서 추출되지 않아도 입력의 버킷 내 원소의 제곱의 합이 전체 원소에 대해 선형이기만 하면 버킷 정렬은 선형 시간을 가진다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중