#5-4-8,9 The Art of Computer Programming - 정렬과 검색

이번엔 두 개를 절을 공부할 예정이다.

그중 첫 번째 절은 2 테이프 정렬에 대한 내용이다.

과도한 테이프 작동 없이 병합 공정 수행을 위해서는 보통 세 개의 테이프가 필요한데

두 개만 사용하도록 적당한 효율로 외부 정렬을 수행하는 방법에 대해 알아본다.

 

1. 퀵 정렬 이용

2. 기수 정렬 이용

 

그러고 나서는 한 개의 테이프로만 정렬 가능한지에 대한 여부를 살핀다.

그러나 생각보다 정렬의 성능은 나쁘다.

 

두 번째 절은 디스크와 드럼에 대한 내용이다.

지금까지는 자기 테이프만 고려했지만, 더 유연한 대용량 저장 장치들에 대해 고민하기로 한다.

자기 디스크는 HDD로 많이 사용되니까 꽤 의미가 있는 절일 것 같다.

 

이들의 특징은 다음과 같다.

1. 저장된 정보의 임의의 특정 부분에 빠르게 접근 가능

2. 내부/외부 메모리 사이에서 연속된 워드들로 된 블록들을 빠르게 전송 가능.

 

완전 이진P 트리를 사용해서 병합 패턴을 구현한다.

 

그다음에는 그나마 익숙한 디스크 스트라이핑(띠 분할) 기법에 대한 설명이 나온다.

무작위 띠분할이라는 기법에 대해서도 소개한다.

 

오늘은 여기까지!