4. 외부 정렬(External sort)
1. 외부 정렬의 기본 개념
내부 정렬 알고리즘의 문제점
정렬할 데이터들이 메모리에 저장된다고 가정하면, 파일에 저장된 레코드 수가 많을 경우, 모든 레코드를 메모리에 저장할 수는 없다.
2. Binary Sort/Merge
1. Binary Sort/Merge 특징
Sorting Phase
- 초기 run들을 sorting한 후, 2개의 외부 파일에 저장
Merging Phase
- 각 파일에서 하나씩 run을 선택하여 큰 run으로 병합하여 세 번째 파일에저장
- 결과 파일을 다시 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
