4. 외부 정렬(External sort)

1. 외부 정렬의 기본 개념

내부 정렬 알고리즘의 문제점

정렬할 데이터들이 메모리에 저장된다고 가정하면, 파일에 저장된 레코드 수가 많을 경우, 모든 레코드를 메모리에 저장할 수는 없다.

2. Binary Sort/Merge

1. Binary Sort/Merge 특징

Sorting Phase

1. 초기 run들을 sorting한 후, 2개의 외부 파일에 저장

Merging Phase

1. 각 파일에서 하나씩 run을 선택하여 큰 run으로 병합하여 세 번째 파일에저장

2. 결과 파일을 다시 2 개의 파일로 분배한 후 병합 진행

2. Binary Sort/Merge의 예

Run = 3 으로 값을 주었기 때문에 File 당 최대 3개의 run 을 받을 수 있다.

3. Balanced Binary Sort/Merge

1. Balanced Binary Sort/Merge 특징

입력 파일 수 = 출력 파일 수 = 2
파일 수가 동일하므로, 파일의 재분배가 필요 없습니다.

4. Balanced K-way Sort/Merge

 k-way Sort/Merge의 Balanced version
 파일 수가 증가하므로 더 적은 수의 병합과 run 가짐
 k의 값이 무한히 증가할 수 있는가?

5. Polyphase Sort/Merge

6. 내용 정리 하기

초기 run의 수가 R인 Binary Sort/Merge
 Level의 수 = log2R + 1
 전체 병합 단계의 수 = log2R

초기 run의 수가 R인 k-way Sort/Merge
 전체 병합 단계의 수 = logkR
 k개의 run에서 가장 작은 key 값을 갖는 run 검색
 Linear search: 전체 비교 수 = n (k – 1) logkR
 Selection tree: 전체 비교 수 = n (log2k)(logkR) = n * log2R

7. 문제 풀어보기

아래 데이터를 갖는 입력 파일을 정렬하고자 한다 메모리에 개의 레코드만 저장할 수 있다고 가정할 때 run generation algorithm으로 생성되는 첫 번째 런의 내용은 무엇인가?

입력 파일: 109 49 34 68 45 2 60 38 78 47 96 19 34 55