11장 집합, 정렬, 선택(2)

11.3 정렬의 하한

여기까지 정렬에 대한 논의를 다시 요약하면, 

크기가 n인 입력 시퀀스에 대해 

O(nlogn)인 최악의 경우 또는 예상 실행 시간을 가진 몇 가지 방법을 설명했다. 

이러한 방법에는 이 장에서 설명하는 병합 정렬과 퀵 정렬뿐만 아니라

8.3.5절에서 설명하는 힙 정렬도 포함된다. 

그렇다면 자연스럽게 할 수 있는 질문은 O(nlogn) 시간보다 더 빠른 정렬이 가능한가 하는 것이다.

이 절에서는 정렬 알고리즘이 사용하는 계산 기본값이 두 요소를 비교하는 것이라면, 

비교 기반 정렬이 실행 시간에 Ω(nlogn) 최악의 경우 하한값을 갖는다는 것을 보여준다. 

(섹션 4.2.3의 표기법 Ω(·)을 참조하라.)

비교 기반 정렬의 주요 비용에 초점을 맞추기 위해, 정렬 알고리즘이 수행하는 비교만 계산해 보겠다. 

하한값을 도출하고 싶으므로, 이 정도면 충분하다.

정렬하고자 하는 수열 S = (x0,x1,<...>xn-1)가 주어지고, 

S의 모든 원소가 서로 다르다고 가정하자 

(하한선을 유도하는 것이므로 이것은 실제로 제한이 아니다). 

비교만 계산하기 때문에 하한을 위해 S가 배열 또는 연결 리스트로 구현되었는지는 신경 쓰지 않는다. 

정렬 알고리즘이 두 원소 xi와 xj를 비교할 때마다 (즉, xi < xj?)

"예" 또는 "아니오"라는 두 가지 결과가 나온다. 

이 비교 결과를 바탕으로 정렬 알고리즘은 일부 내부 계산을 수행할 수 있으며(여기서는 계산하지 않음), 

결국 S의 다른 두 요소 간의 또 다른 비교를 수행하여 다시 두 결과를 얻을 수 있다. 

따라서 비교 기반 정렬 알고리즘을 의사 결정 트리 T로 나타낼 수 있다(그림 7.8). 

즉, T의 각 내부 노드 v는 비교에 해당하고 

노드에서 하위 노드까지의 가장자리는 "예" 또는 "아니오" 답변으로 인한 계산에 해당한다

(그림 11.15 참조).

문제의 가상 정렬 알고리즘은 트리 T에 대한 명시적인 지식이 없을 수 있다는 점에 유의해야 한다.

T를 사용하여 정렬 알고리즘이 수행을 종료하기 직전에 

첫 번째 비교(루트와 관련된)에서 시작하여 마지막 비교(외부 노드의 상위와 관련된)로 끝나는

모든 가능한 비교 시퀀스를 나타낸다.

S의 원소들에 대한 각각의 가능한 초기 순서 또는 순열(permutation)은 

우리의 가상 정렬 알고리즘으로 하여금

T의 경로를 루트에서 어떤 외부 노드로 가로지르며 일련의 비교를 실행하게 할 것이다. 

T의 각 외부 노드 v와 연관시키고, 

정렬 알고리즘을 v로 만드는 S의 순열 집합을 v로 끝내도록 하자. 

하한 논법에서 가장 중요한 관찰은 

T의 각 외부 노드 v가 최대 하나의 S의 순열에 대한 비교 순서를 나타낼 수 있다는 것이다. 

 

이 주장의 정당성은 간단하다. 

만약 S의 서로 다른 두 순열 P1과 P2가 동일한 외부 노드에 연관되어 있다면, 

적어도 두 개의 객체 xi와 xj가 존재하므로, 

P1에서 xj 앞에 xi가 있고 P2에서 xj 뒤에 xi가 있다. 

동시에 v와 연관된 출력은 S의 특정한 순서 변경이어야 하며, 

xi 또는 xj 중 하나가 다른 것 앞에 나타나야 한다. 

그러나 P1과 P2가 모두 정렬 알고리즘으로 S의 원소들을 이 순서로 출력하게 만든다면, 

이것은 알고리즘이 잘못된 순서로 xi와 xj를 출력하도록 속이는 방법이 있음을 의미한다. 

이것은 올바른 정렬 알고리즘에 의해 허용될 수 없으므로, 

T의 각 외부 노드는 S의 순열 하나와 정확히 연관되어야 한다. 

다음 결과를 증명하기 위해 정렬 알고리즘과 연관된 결정 트리의 특성을 사용한다:

제안 11.4: 

n-요소 시퀀스를 정렬하는 모든 비교 기반 알고리즘의 실행 시간은 최악의 경우 Ω(nlogn)이다.

정당성: 

비교 기반 정렬 알고리즘의 실행 시간은 위에서 설명한 바와 같이 

이 알고리즘과 관련된 의사 결정 트리 T의 높이보다 크거나 같아야 한다. 

(그림 11.15 참조) 

위의 인수에 의해, T의 각 외부 노드는 S의 하나의 치환과 연결되어야 한다. 

또한, S의 각 치환은 T의 다른 외부 노드를 생성해야 한다. 

n개 객체의 치환 수 = n! = n(n - 1)(n - 2) ... 2 · 1

따라서, T는 적어도 n!개의 외부 노드를 가져야 한다. 

명제 7.10에 의해, T의 높이는 적어도 log(n!)이다. 

즉, 곱 n!에 n/2보다 크거나 같은 n/2개 이상의 항이 있으므로, 

이것은 제안을 즉시 정당화한다. 따라서

즉, Ω(nlogn)이다.

그림 11.15: 비교 기반 정렬의 하한값 시각화.

11.4 버킷 정렬 및 기수 정렬

앞 절에서 비교 기반 정렬 알고리즘으로 n개의 요소를 가진 시퀀스를 정렬하려면 

최악의 경우 Ω(nlogn) 시간이 필요하다는 것을 보여주었다. 

그렇다면 자연스러운 질문은 

O(nlog) 시간보다 점근적으로 빠르게 실행되도록 설계할 수 있는 

다른 종류의 정렬 알고리즘이 있는지 여부이다.

흥미롭게도 그런 알고리즘이 존재하지만, 

그런 알고리즘을 정렬하려면 입력 순서에 대한 특별한 가정이 필요하다. 

그렇더라도 실제로 그런 시나리오가 종종 발생하기 때문에 이를 논의해 볼 가치가 있다. 

이 절에서는 입력 순서를 각각 키-값 쌍으로 정렬하는 문제를 고려한다.

11.4.1 버킷 정렬

어떤 정수 N ≥ 2에 대하여 키가 [0,N - 1] 범위의 정수인 n개 원소의 수열 S를 생각하고, 

S를 원소의 키에 따라 정렬해야 한다고 가정하자. 

이 경우 S를 O(n + N) 시간에 정렬하는 것이 가능하다. 

놀랍게 보일지 모르지만, 

이것은 예를 들어 N이 O(n)이면 S를 O(n) 시간에 정렬할 수 있다는 것을 의미한다. 

물론 중요한 점은 원소의 형식에 대한 제한적인 가정 때문에 비교를 피할 수 있다는 것이다.

버킷 정렬(bucket-sort):

0부터 N - 1의 색인을 갖는 셀들을 갖는 버킷 배열 B에 키를 인덱스로 사용한다. 

키가 k인 엔트리는 그 자체로 (키가 k인 엔트리들의) 수열인 "버킷" B[k]에 배치된다. 

1) 입력 시퀀스 S의 각 엔트리를 버킷에 삽입한 후, 

2) 버킷 B[0], B[1],...,B[N - 1]의 내용을 순서대로 열거함으로써 

3) 엔트리들을 정렬된 순서로 S에 다시 넣을 수 있다. 

 

코드 조각 11.8에서 버킷 정렬 알고리즘을 설명한다.
코드 조각 11.8: 버킷 정렬.

Algorithm bucketSort(S):

       Input: Sequence S of entries with integer keys in the range [0, N - 1]

       Output: Sequence S sorted in nondecreasing order of the keys

       let B be an array of N sequences, each of which is initially empty

       for each entry e in S do

           k ← e.getKey()

           remove e from S and insert i at the end bucket (sequence) B[k]

       for i ← 0 to N - 1 do

           for each entry e in sequence B[i] do

               remove e from B[i] and insert it at the end of S

버킷 정렬의 실행 시간: O(n + N)

버킷 정렬의 공간 사용: O(n + N)

따라서 버킷 정렬은 키 값의 범위 N이 시퀀스 크기 n에 비해 작을 때 효율적이다

(예: N = O(n) 또는 N = O(nlogn)). 

하지만 N이 n에 비해 커질수록 성능이 저하된다.

버킷 정렬 알고리즘의 중요한 특성은 

같은 키를 가진 여러 요소가 있더라도 올바르게 작동한다는 것이다. 

안정 정렬

키-값 쌍을 정렬할 때 중요한 문제는 키를 얼마나 동일하게 취급하느냐이다. 

S = ((k0,x0),..., (kn-1,x(n-1)))을 이러한 엔트리의 시퀀스라고 가정해 보겠다. 

정렬 알고리즘은

S의 임의의 두 엔트리 (ki,xi)와 (kj,xj)가 

정렬하기 전에 S에서 ki = kj와 (ki,xi)가 (kj,xj)보다 선행하는 경우 (즉, i < j), 

정렬 후에 엔트리 (ki,xi)가 엔트리 (kj,xj)보다 선행하는 경우 

안정적(stable)이라고 한다. 

 

응용 프로그램이 동일한 키로 요소의 초기 순서를 유지하기를 원할 수 있기 때문에 

정렬 알고리즘에 있어서 안정성이 중요하다.

코드 조각 11.8의 버킷 정렬에 대한 비공식적인 설명이

안정성을 보장하는 것은 아니다. 

그러나 O(n + N) 실행 시간을 유지하면서 

버킷 정렬을 안정적으로 만들기 위해 설명을 쉽게 수정할 수 있기 때문에 

이것은 버킷 정렬 메소드 자체에 내재되어 있지 않다. 

실제로 알고리즘을 실행하는 동안 

시퀀스 S와 시퀀스 B[i]에서 항상 첫 번째 요소를 제거하여 

안정적인 버킷 정렬 알고리즘을 얻을 수 있다.

 

11.4.2 기수 정렬

안정적인 정렬이 매우 중요한 이유 중 하나는 

버킷 정렬 접근법을 정수를 정렬하는 것보다 

더 일반적인 컨텍스트에 적용할 수 있기 때문이다. 

예를 들어 일부 정수 N ≥ 2에 대해 

쌍(k,l)인 키(여기서 k와 l은 [0,N - 1] 범위의 정수)로 

항목을 정렬하려고 한다고 가정해 보겠다. 

이와 같은 맥락에서, 이러한 키들에 대해 사전상의(lexicographical) 순서를 정의하는 것은 자연스러운 일이며, 

여기서 (k1,l1) < (k2,l2)가 k1 < k2 또는 k1 = k2 및 l1 < l2 (섹션 8.1.2)인 경우이다.

이것은 일반적으로 동일한 길이의 문자열에 적용되는 사전 비교 함수의 쌍별 버전이다

(그리고 d > 2의 경우 d 숫자의 튜플에 쉽게 일반화된다).

기수 정렬(radix-sort) 알고리즘:

수열에 안정적인 버킷 정렬을 두 번 적용함으로써 수열 S를 쌍인 키로 정렬한다; 

먼저 쌍의 한 성분을 순서 키로 사용하고, 다음으로 두 번째 성분을 사용한다. 

그러나 어떤 순서가 올바른가? 

먼저 k의 (첫 번째 성분) 위에 정렬하고 그 다음에 l의 (두 번째 성분) 위에 정렬해야 할까, 

아니면 반대로 정렬해야 할까?

이 질문에 답하기 전에 다음과 같은 예를 생각해 보자.

예제 11.5: 

S = ((3,3), (1,5), (2,5), (1,2), (2,3), (1,7), (3,2), (2,2))의 순서를 생각해 보자.

첫 번째 성분에서 안정적으로 S를 정렬하면 순서를 얻을 수 있다
S1 = ((1,5), (1,2), (1,7), (2,5), (2,3), (2,2), (3,3), (3,2)).

두 번째 성분을 사용하여 이 시퀀스 S1을 안정적으로 정렬하면 시퀀스를 얻을 수 있다
S1,2 =((1,2), (2,2), (3,2), (2,3), (3,3), (1,5), (2,5), (1,7)),

이것은 정확히 정렬된 순서가 아니다. 

반면에, 두 번째 성분을 사용하여 안정적으로 S를 정렬하면 

S2 = ((1,2), (3,2), (2,2), (3,3), (2,3), (1,5), (2,5), (1,7)) 순서가 나온다.

첫 번째 성분을 사용하여 안정적으로 시퀀스 S2를 정렬하면 시퀀스를 얻을 수 있다

S2,1 = ((1,2), (1,5), (1,7), (2,2), (2,3), (2,5), (3,2), (3,3)),

실제로 사전적으로 순서가 매겨진 시퀀스이다.

따라서, 이 예로부터 우리는 먼저 두 번째 성분을 사용하고 

다시 첫 번째 성분을 사용하여 정렬해야 한다고 생각하게 된다. 

이 직관은 정확하다. 

먼저 두 번째 성분으로 안정적으로 정렬하고 다시 첫 번째 성분으로 정렬함으로써, 

두 원소가 두 번째 성분으로 정렬된 경우 시작 순서에서 상대적인 순서가 보존됨을 보장한다. 

따라서 결과적인 순서는 매번 사전적으로 정렬되는 것이 보장된다. 

이 절을 다음과 같이 요약할 수 있다:

명제 11.6: 

S: n개의 키-값 쌍의 시퀀스

각각의 키: (k1,k2,...,kd)를 가진다.

ki: 어떤 정수 N ≥ 2에 대하여 [0,N - 1] 범위의 정수

기수 정렬을 사용하여 O(d(n + N)) 시간에 S를 사전적으로 정렬할 수 있다.

11.5 정렬 알고리즘 비교

이 시점에서  n-요소 배열 리스트, 노드 리스트 또는 일반 시퀀스를 정렬하기 위해 

이 책에서 연구한 모든 알고리즘을 잠시 생각해 보는 것이 유용할 수 있다.

실행 시간 및 기타 요인 고려

평균적인 경우와 최악의 경우에

O(n^2) 시간 거동을 갖는 삽입 정렬, 선택 정렬과 같은 여러 방법을 연구했다. 

힙 정렬, 병합 정렬, 퀵 정렬을 포함한 O(n logn) 시간 거동을 갖는 여러 방법도 연구했다. 

마지막으로, 저희는 특정 타입의 키에 대해 선형 시간으로 실행되는 특별한 분류 알고리즘, 

즉 버킷 정렬 및 기수 정렬 방법을 연구했다. 

물론 선택 정렬 알고리즘은 최상의 경우에도 O(n^2) 시간으로 실행되므로 

어떤 응용 분야에서도 좋지 않은 선택이다. 

하지만 나머지 정렬 알고리즘 중에서 어느 것이 가장 좋을까?

특정 응용 프로그램에 가장 적합한 정렬 알고리즘은 해당 응용 프로그램의 여러 속성에 따라 달라진다. 

따라서, "좋은" 정렬 알고리즘의 알려진 속성에 기초하여 몇 가지 지침과 관찰을 제공할 수 있다.

삽입 정렬

잘 구현되면 삽입 정렬의 실행 시간은 O(n + m)이다.

m: 반전의 수(즉, 원소 쌍의 수)

따라서 삽입 정렬은 프로그래밍하기 쉽고 작은 시퀀스는 반드시 반전이 거의 없기 때문에 

작은 시퀀스(예: 50개 미만의 원소)를 정렬하는 데 탁월한 알고리즘이다. 

또한 삽입 정렬은 이미 "거의" 정렬된 시퀀스를 정렬하는 데 상당히 효과적이다. 

"거의" 우리는 반전의 수가 적다는 것을 의미한다. 

그러나 삽입 정렬의 O(n^2) 시간 성능은 이러한 특수한 맥락을 벗어나는 경우에는 좋지 않은 선택이다.

병합 정렬

반면 병합 정렬은 최악의 경우 O(n logn) 시간에 실행되므로

비교 기반 정렬 방법에 최적이다. 

하지만 실험 연구에 따르면 

병합 정렬을 제자리에서 실행하기 어렵기 때문에 

병합 정렬을 구현하는 데 필요한 오버헤드가 

컴퓨터의 주 메모리 영역에 전체적으로 들어갈 수 있는 시퀀스에 대한 

힙 정렬 및 퀵 정렬의 제자리 구현보다 덜 매력적인 것으로 나타났다. 

그럼에도 병합 정렬은 입력이 모두 주 메모리에 들어갈 수는 없지만 

디스크와 같은 외부 메모리 장치의 블록에 저장되어야 하는 상황에서 탁월한 알고리즘이다.

이러한 컨텍스트에서 긴 병렬 스트림에서 데이터의 실행을 병합 정렬 처리하는 방식은 

디스크의 블록에 있는 메인 메모리로 가져온 모든 데이터를 최대한 활용한다. 

따라서 외부 메모리 정렬을 위해 병합 정렬 알고리즘은 

필요한 디스크 읽기 및 쓰기의 총 수를 최소화하는 경향이 있으므로 

이러한 컨텍스트에서 병합 정렬 알고리즘이 우수하다.

퀵 정렬

실험 연구에 따르면 입력 시퀀스가 완전히 메인 메모리에 들어갈 수 있다면 

퀵 정렬과 힙 정렬의 제자리 버전이 병합 정렬보다 더 빠르게 실행된다. 

노드나 항목을 복사하는 데 필요한 추가 오버헤드 때문에 

이러한 응용 프로그램에서는 병합 정렬이 퀵 정렬과 힙 정렬에 불리하다. 

사실 이러한 테스트에서는 퀵 정렬이 힙 정렬을 능가하는 경향이 있다.

따라서 퀵 정렬은 범용 메모리 내 정렬 알고리즘으로 탁월한 선택이다. 

실제로 C 언어 라이브러리에 제공되는 q 정렬 유틸리티에 포함되어 있다. 

그러나 O(n^2) 시간 최악의 성능으로 인해 

정렬 작업을 완료하는 데 필요한 시간을 보장해야 하는 

실시간 응용 프로그램에서 퀵 정렬을 선택하는 것은 좋지 않다.

힙 정렬

힙 정렬 알고리즘은 정렬 작업을 수행할 시간이 정해져 있고 

입력 데이터가 메인 메모리에 들어갈 수 있는 

실시간 시나리오에서는 아마도 가장 적합한 방법일 것이다. 

O(nlogn) 최악의 경우 시간 내에 실행되며 제자리에서 쉽게 실행할 수 있다.

버킷 정렬 및 기수 정렬

마지막으로, 응용 프로그램이 작은 정수 키 또는 

작은 정수 키의 d-튜플로 항목을 정렬하는 것을 포함하는 경우 

버킷 정렬 또는 기수 정렬이 우수한 선택이다. 

O(d(n + N) 시간에 실행되므로 

[0,N - 1]은 정수 키의 범위(버킷 정렬의 경우 d = 1)이다. 

따라서 d(n + N)이 nlogn 함수보다 훨씬 "아래에" 있는 경우 

이 정렬 방법은 퀵 정렬 또는 힙 정렬보다 빠르게 실행되어야 한다.

따라서 이러한 모든 다양한 정렬 알고리즘에 대한 연구는 

알고리즘 엔지니어링 "툴박스"에서 다양한 정렬 방법 모음을 제공한다

11.6 집합 ADT 및 조합/구조체 찾기

이 절에서는 집합 ADT를 소개한다. 

집합(set): 서로 다른 객체들의 모임

즉, 집합 내에는 중복되는 원소들이 없으며, 

키에 대한 명시적인 개념이나 심지어 순서도 없다. 

정렬이 집합 ADT의 연산을 효율적으로 구현하는 데 중요한 역할을 할 수 있기 때문에, 

집합에 대한 논의를 정렬에 관한 장에 포함시킨다.

집합 및 일부 용도

먼저 두 집합 A와 B의

합집합(union), 교집합(intersection), 뺄셈(subtraction)에 대한 수학적 정의를 떠올린다:
A ∪ B = {x: x is in A or x is in B},
A ∩ B = {x: x is in A and x is in B}, 

A − B = {x: x is in A and x is not in B}.

예 11.7: 대부분의 인터넷 검색 엔진은

사전 데이터베이스에 있는 각 단어 x에 대해 

각 웹 페이지가 고유한 인터넷 주소로 식별되는 

x를 포함하는 웹 페이지의 집합 W(x)를 저장한다.

단어 x에 대한 쿼리와 함께 제공되는 검색 엔진은 

페이지 "중요도"의 고유 우선 순위에 따라 

정렬된 집합 W(x)의 웹 페이지만 반환하면 된다. 

그러나 단어 x와 y에 대한 두 단어 쿼리가 제공되는 경우 

이러한 검색 엔진은 먼저 교차점 W(x) ∩ W(y)를 계산한 다음 

우선 순위별로 정렬된 결과 집합의 웹 페이지를 반환해야 한다. 

이 계산을 위해 여러 검색 엔진이 이 섹션에서 설명하는 설정된 교차점 알고리즘을 사용한다.

집합 ADT의 기본적인 방법

집합 A에 작용하는 집합 ADT의 기본적인 방법은 다음과 같다: 

union(B): A를 A와 B의 합집합으로 대체, 즉 A ← A ∪ B를 실행한다.
intersect(B): A를 A와 B의 교집합으로 바꾸어, 즉 A ← A ∩ B를 실행한다.
subtract(B): A를 A와 B의 차집합로 대체, 즉 A ← A - B를 실행한다.

11.6.1 간단한 집합 구현

집합을 구현하는 가장 간단한 방법 중 하나는 집합의 원소들을 순서대로 저장하는 것이다. 

이 구현은 예를 들어 일반적인 자료 구조를 위한 여러 소프트웨어 라이브러리에 포함되어 있다. 

따라서 집합 ADT를 순서 순서대로 구현하는 것을 고려해 보겠다

(몇 가지 연습문제에서 다른 구현을 고려한다). 

모든 집합에 동일한 순서가 사용되는 경우 

집합의 원소들 간의 임의의 일관된 전체 순서 관계가 사용될 수 있다.

입력 집합들을 나타내는 정렬된 두 수열을 입력으로 하는 

병합 알고리즘의 일반적인 버전을 사용하여 

세 가지 기본 집합 연산을 각각 구현하고, 

입력 집합들의 합집합, 교집합, 뺄셈 등 출력 집합을 나타내는 수열을 구성한다. 

또한, 이러한 연산들을 정의하여 집합 A의 내용을 수정했다. 

또는 이러한 방법들이 A를 수정하지 않고 새로운 집합을 반환하도록 정의할 수도 있었다.

일반 병합 알고리즘은 

입력 시퀀스 A와 B의 현재 원소 a와 b를 각각 반복적으로 검사하고 비교하여 

a < b, a = b, 또는 a > b 중 어느 하나를 출력 시퀀스 C의 끝에 복사해야 하는지 결정한다. 

이 결정은 우리가 수행하고 있는 특정 연산, 즉 합집합, 교집합, 뺄셈에 따라 이루어진다. 

예를 들어 합집합 연산에서는 다음과 같이 진행한다:

• a < b이면, 우리는 a를 C의 끝에 복사하고 A의 다음 원소로 나아간다.
• a = b이면, 우리는 a를 C의 끝까지 복사하고 A와 B의 다음 원소로 나아간다.
• a > b이면, 우리는 b를 C의 끝까지 복사하고 B의 다음 원소로 나아간다.

일반적인 병합의 성능

일반적인 병합의 실행 시간을 분석해 보겠다. 

각 반복에서 입력 시퀀스 A와 B의 두 요소를 비교하여 

한 요소를 출력 시퀀스에 복사하고 

A, B, 또는 둘 다의 현재 요소를 발전시킨다.

요소를 비교하고 복사하는 데 O(1) 시간이 걸린다고 가정하면, 

총 실행 시간은 O(nA + nB)이며, 

nA: A의 크기, nB: B의 크기

즉, 일반적인 병합은 요소의 수에 비례하는 시간이 소요된다. 

따라서 다음과 같은 것이 있다:

제안 11.8: 

집합 ADT는 순서화된 시퀀스와 O(n) 시간의 연산 결합, 

교차 및 감산을 지원하는 일반 병합 방식으로 구현될 수 있다. 

n: 관련된 집합들의 크기의 합

템플릿 메소드 패턴으로서의 일반 병합

일반적인 병합 알고리즘은 템플릿 메소드 패턴을 기반으로 한다(Section 7.3.7 참조). 

 

템플릿 메소드 패턴(template method pattern):

특정 단계를 재정의하여 특화할 수 있는 

일반적인 계산 메커니즘을 설명하는 소프트웨어 엔지니어링 설계 패턴

 

이 경우 두 시퀀스를 하나로 병합하는 메소드를 설명하며 

세 가지 추상 메소드의 동작으로 특화할 수 있다.

코드 조각 11.9는 일반적인 병합 알고리즘의 자바 구현을 제공하는 Merge 클래스를 보여준다.

코드 조각 11.9: 일반 병합을 위한 클래스 Merge.

/** Generic merge for sorted sequence. */
public abstract class Merge<E> {
  private E a, b;                    // current elements in A and B
  private Iterator<E> iterA, iterB;  // iterators for A and B
  /** Template method */
  public void merge(PositionList<E> A, PositionList<E> B,
       Comparator<E> comp, PositionList<E> C) {
    iterA = A.iterator();
    iterB = B.iterator();
    boolean aExists = advanceA();  // Boolean test if there is a current a
    boolean bExists = advanceB();  // Boolean test if there is a current b
    while (aExists && bExists) {   // Main loop for merging a and b
      int x = comp.compare(a, b);
      if (x < 0) { alsLess(a, C); aExists = advanceA(); }
      else if (x == 0) {
        bothAreEqual(a, b, C); aExists = advanceA(); bExists = advanceB(); }
      else { blsLess(b, C); bExists = advanceB(); }
    }
    while (aExists) { alsLess(a, C); aExists = advanceA(); }
    while (bExists) { blsLess(b, C); bExists = advanceB(); }
  }
  // auxiliary methods to be specialized by subclasses
  protected void alsLess(E a, PositionList<E> C) { }
  protected void bothAreEqual(E a, E b, PositionList<E> C) { };
  protected void blsLess(E b, PositionList<E> C) { }
  // auxiliary methods
  private boolean advanceA() {
    if (iterA.hasNext()) { a = iterA.next(); return true; }
    return false;
  }
  private boolean advanceB() {
    if (iterB.hasNext()) { b = iterB.next(); return true; }
    return false;
  }
}

일반적인 Merge 클래스를 유용한 클래스로 변환하기 위해서는 

aIsLess, bothAreEqual, bIsLess 세 가지 보조 메소드를 재정의하는 클래스로 확장해야 한다. 

코드 조각 11.10에서 이러한 메소드를 통해 

합집합, 교집합, 차집합을 쉽게 설명할 수 있는 방법을 보여준다. 

템플릿 메소드 merge가 다음과 같이 수행되도록 보조 메소드가 재정의된다:

• 클래스 UnionMerge에서 merge는 A와 B의 모든 요소를 C로 복사하지만 어떤 요소도 복제하지 않는다.
• 클래스 IntersectMerge에서 merge는 A와 B 모두에 있는 모든 요소를 C로 복사한다.

   하지만 한 집합에서는 요소를 "버리"지만 다른 집합에서는 요소를 복사하지 않는다.
• 클래스 SubtractMerge에서 merge는 A에 있고 B에 있지 않은 모든 요소를 C로 복사한다.

코드 조각 11.10 : 

각각 설정된 합집합, 교집합, 차집합을 수행할 보조 메소드를 전문화하여 

Merge 클래스를 확장하는 클래스

/** Class specializing the generic merge template to union two sets. */
public class UnionMerge<E> extends Merge<E> {
  protected void alsLess(E a, PositionList<E> C) { 
    C.addLast(a);     // add a
  }
  protected void bothAreEqual(E a, E b, PositionList<E> C) { 
    C.addLast(a);     // add a (but not duplicate b)
  }
  protected void blsLess(E b, PositionList<E> C) { 
    C.addLast(b);     // add b
  }
}
/** Class specializing the generic merge template to intersect two sets. */
public class IntersectMerge<E> extends Merge<E> {
  protected void alsLess(E a, PositionList<E> C) { }
  protected void bothAreEqual(E a, E b, PositionList<E> C) { 
    C.addLast(a);     // add a (but not duplicate b)
  }
  protected void blsLess(E b, PositionList<E> C) { }
}
/** Class specializing the generic merge template to subtract two sets. */
public class UnionMerge<E> extends Merge<E> {
  protected void alsLess(E a, PositionList<E> C) { 
    C.addLast(a);     // add a
  }
  protected void bothAreEqual(E a, E b, PositionList<E> C) { }
  protected void blsLess(E b, PositionList<E> C) { }
}

11.6.2 Union-find 연산이 포함된 파티션

파티션(partiton): 서로소인 집합들의 컬렉션

각각의 원소 x를 저장하는 위치 객체를 사용하여 파티션 ADT의 메소드를 정의한다(섹션 6.2.2). 

파티션 ADT는 다음 메소드를 지원한다.

makeSet(x): 원소 x를 포함하는 단일 톤 집합을 만들고 이 집합에서 x를 저장하는 위치를 반환한다.
union(A, B): 세트 A B를 반납하여 기존의 A와 B를 파괴한다.
find(p): p 위치에 있는 요소를 포함하는 집합을 반환한다.

총 n개의 원소를 가진 파티션을 간단히 구현하면 

집합 A에 대한 수열이 집합의 원소로 설정된 위치를 저장하는 수열 집합이 있다. 

각 위치 객체는 변수, 요소를 저장하는데, 

요소는 해당 요소 x를 참조하고

O(1) 시간으로 element() 메소드를 실행할 수 있다. 

또한 이 수열은 p의 원소를 포함하는 집합을 나타내기 때문에

각 위치에 집합의 변수 p를 저장한다.

 

(그림 11.16 참조) 따라서 p에 대한 설정된 기준을 따름으로써 

연산 find(p)를 O(1) 시간에 수행할 수 있다. 

마찬가지로 makeSet도 O(1) 시간이 걸린다. 

연산 union(A,B)를 사용하려면 

두 개의 시퀀스를 하나로 연결하고 

둘 중 하나의 위치에 대한 set 참조를 업데이트해야 한다. 

더 작은 크기의 시퀀스에서 모든 위치를 제거하고 

더 큰 크기의 시퀀스에 삽입하여 이 연산을 구현하기로 선택한다. 

더 작은 집합에서 한 위치 p를 가져와 더 큰 집합 t에 삽입할 때마다 

p에 대한 설정된 기준을 지금 t로 업데이트한다. 

따라서 연산 union(A,B)는 O(n)인 시간이 소요되는데, 

이는 최악의 경우 |A| = |B| = n/2이기 때문이다. 

그럼에도 불구하고 다음과 같이 분할 분석을 통해 

이 구현이 최악의 경우 분석에서 나타난 것보다 훨씬 더 나은 것으로 나타났다.

 

그림 11.16:

A = 1,4,7, B = 2,3,6,9 및 C = 5,8,10,11,12의 

세 세트로 구성된 파티션의 시퀀스 기반 구현.

 

시퀀스 구현의 성능

위의 수열 구현은 간단하지만 다음 정리에서 알 수 있듯이 효율적이기도 하다.

제안 11.9: 

n개의 makeSet, union, find 연산을

위의 시퀀스 기반 구현을 사용하여 초기 빈 파티션에서 시작하여 O(nlog) 시간이 걸린다.

정당성: 

회계 메소드를 사용하고

하나의 사이버 달러가 find 연산, makeSet 연산 또는

union 연산에서 한 시퀀스에서 다른 시퀀스로 위치 객체의 이동을 수행하는 데

시간을 지불할 수 있다고 가정한다.

find 또는 makeSet 연산 - 연산 자체에 1 사이버 달러를 청구한다. 

union 연산 - 한 세트에서 다른 세트로 이동하는 각 위치에 1 사이버 달러를 청구한다. 

union 연산 자체에 대해서는 아무런 청구도 하지 않는다. 

find와 makeSet 연산의 총 청구액: O(n)

그렇다면 union의 연산을 대신하여 주어진 위치에 대한 전하량을 생각해 보자. 

중요한 관찰은 한 집합에서 다른 집합으로 한 위치를 옮길 때마다 

새로운 집합의 크기는 적어도 두 배가 된다는 것이다. 

따라서 각 위치는 최대 logn번 한 집합에서 다른 집합으로 이동하게 되고, 

따라서 각 위치는 최대 O(logn)번 충전될 수 있다. 

분할이 처음에 비어 있다고 가정하기 때문에 

주어진 일련의 연산에서 언급된 O(n)개의 다른 원소들이 존재한다. 

모든 union의 연산에 대한 총 시간: O(nlogn)

(makeSet, union, find 연산에서 분할 상환 실행 시간)

= (총 연산에 소요된 시간) / (연산의 수)

위의 명제로부터 시퀀스를 사용하여 구현된 파티션의

각 연산의 분할 상환된 실행 시간은 O(logn)이라는 결론을 얻을 수 있다. 

따라서 간단한 시퀀스 기반 파티션 구현의 성능을 다음과 같이 요약할 수 있다.

 

제안 11.10: 

n개의 makeSet, union, find 연산의 파티션의 시퀀스 기반 구현을 사용하여 

초기 빈 파티션에서 시작하는 일련의 작업에서 각 작업의 분할 상환 실행 시간은 O(logn)이다.

파티션의 시퀀스 기반 구현에서 각 find 연산은 최악의 경우 O(1) 시간이 소요된다. 

계산 병목 현상은 union 연산의 실행 시간이다.

다음 섹션에서는 일정한 시간 find 작업을 보장하지 않지만 

union 작업당 O(logn)보다 훨씬 더 나은 분할 상환 시간을 갖는 파티션의 트리 기반 구현에 대해 설명한다.

11.6.3 트리 기반 파티션 구현

대안적인 자료 구조는 트리의 컬렉션을 사용하여 n개의 요소를 집합으로 저장하고

각 트리는 서로 다른 집합과 연결된다. 

(그림 11.17 참조) 

특히 각 트리를 노드 자체가 설정된 위치 객체인 연결된 자료 구조로 구현한다. 

여전히 이전과 같이,

각 위치 p를

요소 x를 참조하는 요소 변수와

x를 포함하는 집합을 참조하는 집합 변수를 갖는

노드로 보고 있다.

그러나 이제 각 위치 p를 "집합" 데이터 타입의 것으로도 보고 있다. 

따라서 각 위치 p의 집합 참조는 p 자체일 수도 있는 위치를 가리킬 수 있다. 

또한 모든 위치와 각 위치의 집합 참조가 함께 트리의 컬렉션을 정의하도록 이 접근 방식을 구현한다.

각 트리를 집합과 연관시킨다. 

임의의 위치 p에 대하여, 

만약 p의 집합이 다시 p를 가리키면, 

p는 그 트리의 루트이고, p를 포함하는 집합의 이름은 "p"이다. 

(즉, 이 경우에는 위치 이름을 집합 이름으로 사용한다.)

그렇지 않으면, p에 대한 집합의 참조는 그것의 트리에 있는 p의 부모를 가리킨다. 

어느 경우에나, p를 포함하는 집합은 p를 포함하는 트리의 루트와 연관된 것이다.

그림 11.17: A = 1,4,7, B = 2,3,6,9 및 C = 5,8,10,11,12의 

3개의 서로소 집합으로 구성된 파티션의 트리 기반 구현.

이 파티션 자료 구조를 사용하면 

집합 A와 B(즉, A = p와 B = q)를 각각 나타내는 

위치 인수 p와 q를 사용하여 연산 union(A,B)을 호출한다. 

트리 중 하나를 다른 트리의 하위 트리로 만들어 이 연산을 수행한다(그림 11.18b). 

한 트리의 루트의 집합 참조를 다른 트리의 루트를 가리키도록 설정하여 

O(1) 시간 내에 수행할 수 있다. 

위치 p에 대한 연산 find는 

위치 p를 포함하는 트리의 루트까지 걸어 올라가 수행되며(그림 11.18a), 

최악의 경우 O(n) 시간이 걸린다.

트리의 이 표현은 파티션을 구현하는 데 사용되는 전문화된 자료 구조이며 

트리 추상 데이터 타입을 구현하는 것을 의미하지 않다(섹션 7.1). 

실제로 이 표현은 "상향" 링크만 있을 뿐 

특정 노드의 자식에 접근하는 방법을 제공하지 않다.

그림 11.18: 파티션의 트리 기반 구현: 

(a) 연산 union(A,B); (b) 연산 find(p), p: 요소 12에 대한 위치 객체

 

처음에는 이러한 구현이 시퀀스 기반 자료 구조보다 더 나은 것 같지는 않지만 

다음과 같은 간단한 휴리스틱을 추가하여 더 빠르게 실행할 수 있다:

Union-by-Size(크기에 의한 합집합):

각 위치 노드 p와 함께 하위 트리의 크기를 저장한다. 

union 연산에서 더 작은 set의 트리를 다른 트리의 subtree로 만들고 

결과 트리의 루트의 크기 필드를 업데이트한다.

경로 압축(path compression):

find 연산에서 find가 방문하는 각 노드 v에 대해

부모 포인터를 v에서 루트로 재설정한다(그림 11.19 참조)

 

이러한 휴리스틱은 작업의 실행 시간을 일정한 요소로 증가시키지만, 

아래에서 논의하는 바와 같이 분할 상환된 실행 시간을 크게 향상시킨다.

그림 11.19: 경로 압축 휴리스틱: 

(a) 요소 12의 연산 find에 의해 통과된 경로;  (b) 재구조화된 트리.

로그-스타 및 인버스 아커만 함수

트리 기반 파티션 자료 구조의 놀라운 특성은 

union-by-size 및 경로 압축 휴리스틱을 사용하여 구현할 때 

일련의 n개의 union 및 find 연산을 수행하는 데 0(nlog*n) 시간이 소요된다는 것이다.

log*n: log-star 함수이며, 이는 tower-of-twos 함수의 역이다. 

n의 반복 로그이며 n의 테트레이션(거듭제곱의 반복)의 역이다.

직관적으로 log*n은 2보다 작은 숫자를 얻기 전에 어떤 숫자의 로그(베이스 2)를 반복적으로 취할 수 있는 횟수이다. 

표 11.1은 몇 가지 샘플 값을 보여준다.

표 11.1: log* n의 일부 값과 그 역에 대한 임계 값.

표 11.1에 나와 있는 것처럼, 모든 실용적인 목적을 위해 log* n ≤ 5이다. 

놀랍게도 느리게 성장하는 함수이지만, 그럼에도 불구하고 성장하는 함수이다.

실제로 위와 같이 구현된 

일련의 n개 분할 연산의 실행 시간은 

실제로 O(nα(n))로 보일 수 있으며, 

여기서 α(n)는 아커만 함수(Ackermann function) A의 역수이며, 

log*n보다 점근적으로 더 느리게 성장한다. 

이 사실을 증명하지는 않겠지만, 

여기서는 아커만 함수가 얼마나 빨리 성장하는지, 

따라서 역수가 얼마나 느리게 성장하는지 이해하기 위해 아커만 함수를 정의하겠다. 

먼저 인덱스화된 아커만 함수 Ai를 다음과 같이 정의한다:

A0(n)= 2n                      (n≥0일 때)
Ai(1)= A(i−1)(2)             (i≥1일 때)
Ai(n)=A(i−1)(Ai(n−1))    (i≥1 그리고 n≥2일 때)
즉, 아커만 함수는 함수의 진행을 정의한다:
• A0(n) = 2n은 곱하기 2 함수이다
• A1(n) = 2n은 2의 거듭제곱 함수이다
• A2(n) = 수학(n이 2인 경우)은 tower-of-twos(2의 거듭제곱의 반복) 함수이다
• 등등.

그런 다음 아커만 함수를 A(n) = An(n)으로 정의하고, 

이것은 엄청나게 빠르게 증가하는 함수이다. 

마찬가지로, 역 아커만 함수(inverse Ackermann function)도,
α(n) = min{m: A(m) ≥ n},
는 엄청나게 느리게 성장하는 함수이다. 

예를 들어, 이것은 A2(n)의 역수인 log*n 함수보다 훨씬 느리게 성장하는데, 

이미 log*n이 매우 느리게 성장하는 함수라는 것을 주목했다.

11.7 선택

전체 집합의 순서와 관련하여 순위 측면에서 

단일 요소를 식별하는 데 관심이 있는 많은 응용 프로그램이 있다.

예를 들어 최소 요소와 최대 요소를 식별하는 것이 있지만, 

중위 요소를 식별하는 데에도 관심이 있을 수 있다.

 

중위(meidan) 요소: 다른 요소의 절반이 더 작고 나머지 절반이 더 큰 요소

순서 통계(order statistics): 주어진 순위를 가진 요소를 요청하는 쿼리

선택 문제 정의

선택 문제(selection problem):

n개의 비교 가능한 요소의 정렬되지 않은 컬렉션에서

k번째로 작은 요소를 선택하는 일반적인 순서 통계 문제

 

물론 컬렉션을 정렬한 다음 인덱스 k-1에서 정렬된 시퀀스로 인덱싱하여 이 문제를 해결할 수 있다. 

이 방법은 최적의 비교 기반 정렬 알고리즘을 사용하여 O(n logn) 시간이 소요되며, 

이는 k = 1 또는 k = n(또는 심지어 k=2, k=3,k=n-1 또는 k=n-5)인 경우에 대한 과잉이 분명한데, 

이는 이러한 k 값에 대한 선택 문제를 O(n) 시간에서 쉽게 해결할 수 있기 때문이다.

따라서 자연스럽게 질문해야 할 것은 모든 k 값

(여기서 k = ⌊n/2⌋ ; 중간값을 찾는 흥미로운 경우 포함)에 대해 

O(n) 실행 시간을 달성할 수 있는지 여부이다.

11.7.1 Prune-and-Search

이것은 작은 놀라움으로 다가올 수 있지만, 

어떤 k 값에 대해서도 O(n) 시간으로 선택 문제를 해결할 수 있다. 

또한 이 결과를 얻기 위해 사용하는 기법은 흥미로운 알고리즘 설계 패턴을 포함한다. 

 

prune-and-search(가지치기 검색) 또는 decrease-and-conquer(감소와 정복):

n개의 객체 중 일부를 잘라내고 더 작은 문제를 재귀적으로 해결함으로써 

n개의 객체 집합에 정의된 주어진 문제를 해결한다. 

 

마침내 일정한 크기의 객체 집합에 정의된 문제로 문제를 줄이면, 

브루트 포스(brute-force) 방법을 사용하여 문제를 해결한다. 

모든 재귀적 호출을 수행하고 돌아오면 설계가 완료된다. 

경우에 따라 재귀를 사용하는 것을 피할 수 있으며, 

이 경우에는 단순하게 단순한 브루트 포스 방법을 적용하고 멈출 수 있을 때까지

prune-and-search 축소 단계를 반복한다. 

 

또한 9.3.3절에 설명된 이진 탐색 메소드가 prune-and-search 설계 패턴의 예이다.

11.7.2 랜덤화된 퀵셀렉트

랜덤화된 퀵셀렉트(randomized quick-select):

prune-and-search 패턴을 선택 문제에 적용할 때, 

전체 순서 관계가 정의된 n개 요소의 순서 없는 시퀀스에서 k번째로 작은 요소를 찾기 위해 

설계하는 간단하고 실용적인 방법

 

랜덤화된 퀵셀렉트는 O(n) 예상 시간에 실행되며, 

알고리즘에 의해 수행된 모든 가능한 랜덤 선택을 대체하며, 

이 예상은 입력 분포에 대한 랜덤성 가정에 전혀 의존하지 않는다. 

랜덤화된 퀵 셀렉트가 최악의 경우 O(n^2) 시간에 실행되며, 

그 정당성은 연습(R-11.25)으로 남겨진다.

또한 O(n) 최악의 경우 시간에 실행되는 결정론적(deterministic) 선택 알고리즘을 얻기 위해 

랜덤화된 퀵셀렉트를 수정하는 연습문제(C-1.31)도 제공한다. 

그러나 이 경우 big-Oh 표기법에 의해 숨겨진 상수 인자가 상대적으로 크기 때문에 

이 결정론적 알고리즘의 존재는 대부분 이론적 관심거리이다. 

 

정수 k > [1,n]과 함께 n개의 유사한 요소로 구성된 정렬되지 않은 시퀀스 S가 주어졌다고 가정하자. 

높은 수준에서 S에서 k번째로 작은 요소를 찾기 위한 퀵셀렉트 알고리즘은 

11.2.1절에서 설명한 랜덤화된 퀵 정렬 알고리즘과 구조가 유사하다. 

 

1) prune 단계:

임의로 S에서 요소 x를 선택하고 이를 "피벗"으로 사용하여 

S를 세 개의 하위 시퀀스 L, E, G로 세분화하여 

S의 요소를 각각 x보다 작거나 x와 같거나 x보다 큰 값으로 저장한다. 

 

2) 그런 다음 k의 값을 기반으로 이들 집합 중 어떤 것을 반복할지 결정한다. 

 

임의화된 빠른 선택은 코드 단편 11.11에 설명되어 있다. 

 

코드 조각 11.11: 랜덤화된 빠른 선택 알고리즘.

Algorithm quickSelect(S,k):

       Input: Sequence S of n comparable elements, and an integer k ∈ [1,n]

       Output: The kth smallest element of S

       if n = 1 then 

           return the (first) element of S.

       pick a random (pivot) element x of S and divide S into three sequences:

              •L, storing the elements in S less than x

              •E, storing the elements in S equal to x

              •G, storing the elements in S greater than x.

       if k ≤ |L| then 

           quickSelect(L,k)

       else if k ≤ |L| + |E| then 

           return x             {each element in E is equal to x}

       else 

           quickSelect(G,k — |L| — |E|)             {note the new selection parameter}

11.7.3 랜덤화된 퀵셀렉트 분석

랜덤화된 퀵셀렉트가 O(n) 시간에 실행된다는 것을 보여주는 것은 

간단한 확률론적 논법을 필요로 하다. 

그 논법은 X와 Y가 임의 변수이고 c가 숫자이면 다음과 같은 기대의 선형성에 기초한다
E(X + Y)=E(X)+E(Y) 그리고 E(cX)=cE(X),
여기서 우리는 식 Z의 기댓값을 나타내기 위해 E(Z)를 사용한다.

t (n): 크기 n의 수열에 대한 임의화된 퀵 선택의 실행 시간

이 알고리즘은 임의의 사건에 의존하므로 

실행 시간 t(n)은 임의의 변수이다. 

E(t(n)): t(n)의 기댓값

E(t(n))의 경계를 짓고자 한다.

만약 L과 G의 크기가 최대 3n/4가 되도록 S를 분할한다면, 

재귀 호출이 "good"이라고 말하라.

재귀 호출은 분명히 확률 1/2로 good이다.

g(n): good 호출을 받기 전에 현재 호출을 포함하여 연속적으로 재귀 호출한 횟수

그러면 우리는 다음 반복 방정식을 사용하여 t(n)을 특성화할 수 있다:
t(n)≤bn·g(n) + t(3n/4),
여기서 b ≥ 1은 상수이다. 

n > 1에 대한 기대의 선형성을 적용하면,
E (t(n)) ≤E(bn·g(n) + t(3n/4)) =bn·E (g(n)) + E (t(3n/4)).

재귀적 호출은 1/2의 확률로 good이며, 

재귀적 호출의 good 여부는 부모 호출의 good과 무관하므로, 

g(n)의 기대값 = 공정한 동전이 "head"에 떠오르기 전에 뒤집어야 하는 기대 횟수

E(g(n) = 2

따라서, T(n)을 E(t(n))에 대한 약자로 하면, n > 1에 대한 경우를 다음과 같이 쓸 수 있다
T(n)≤T(3n/4) + 2bn.

이 관계를 닫힌 형태로 변환하기 위해

n이 크다고 가정하고 이 부등식을 반복적으로 적용해 보자. 

따라서 예를 들어 두 번 적용한 후 

T(n) ≤ T((3/4)^2 ·n) + 2b(3/4)n + 20bn.
이 시점에서, 우리는 일반적인 경우가

다시 말해서, 예상 실행 시간은 최대 2bn 배로 밑이 1보다 작은 양수인 기하학적 합이다. 

따라서 명제 4.5에 의해 T(n)은 O(n)이다.

제안 11.11: S의 두 요소를 O(1) 시간에 비교할 수 있다고 가정할 때, 

크기 n의 시퀀스 S에 대한 랜덤화된 퀵셀렉트의 예상 실행 시간은 O(n)이다.