실전 정렬의 고려사항

알고리즘(Algorithm) F에 대한 추가 논의는 5.4.9절에서 다룬다.

이제 테이프와 병합(Merge)에 관해 알고 있는 지식을 활용하여, 5.4.2절부터 5.4.5절까지 연구해 온 다양한 병합 패턴의 효율성을 비교해 보자. 각 방법을 동일한 작업에 적용할 때 세부 사항을 면밀히 분석하는 것은 매우 교훈적이다. 따라서 다음과 같은 문제를 고려해 보자: 각 레코드(Record)가 100문자를 포함하는 파일을 정렬하는데, 데이터 저장용으로 사용 가능한 내부 메모리가 100,000자이다 - 프로그램과 보조 변수에 필요한 공간이나, 선택 트리(Selection Tree)의 링크가 차지하는 공간은 제외한다. (

정렬할 레코드의 총 개수는 100,000개이지만, 이 정보는 정렬 알고리즘에 사전에 알려지지 않는다.

정렬할 레코드의 총 개수는 100,000개이지만, 이 정보는 정렬 알고리즘에 사전에 알려지지 않는다.

차트(Chart) A의 펼침 그림은 이 데이터에 10가지 서로 다른 병합 방식을 적용했을 때 일어나는 작업들을 요약한다. 이 중요한 그림을 보는 가장 좋은 방법은 실제로 정렬이 진행되는 것을 지켜보고 있다고 상상하는 것이다: 각 줄을 천천히 왼쪽에서 오른쪽으로 훑으면서, 그림에 표시된 대로 6개의 테이프가 읽고, 쓰고, 되감고, 그리고/또는 역방향으로 읽는 것을 실제로 볼 수 있다고 가정하라. P-방향 병합 동안 입력 테이프는 출력 테이프의 1/P 빈도로만 움직인다. 원래 입력 테이프가 완전히 읽히면 (그리고 "잠금 상태로 되감기"

예제 1. 정방향 읽기 균형 병합(Read-forward Balanced Merge).

예제 1. 정방향 읽기 균형 병합(Read-forward Balanced Merge).

문제의 명세를 복습해 보자: 레코드는 100자 길이이고, 한 번에 1,000개의 레코드를 보관할 만큼의 내부 메모리가 있으며, 입력 테이프의 각 블록에는 5,000자(50개 레코드)가 포함된다. 총 100,000개의 레코드(= 10,000,000자 = 2,000블록)가 있다.

중간 파일의 블록 크기는 자유롭게 선택할 수 있다. 6-테이프 균형 병합은 3-방향 병합을 사용하므로, 알고리즘 F의 기법에 따르면 8개의 버퍼(Buffer)가 필요하다; 따라서 각 블록당 1000/8 = 125개의 레코드(= 12,500자)를 포함하는 블록을 사용할 수 있다.