자료구조의 이해 레포트2

1. 외부 정렬은 정렬하려는 파일의 크기가 너무 커서 주기억 장치에 적재할 수 없어 보조 기억 장치인 디스크나 테이프를 이용하여 정렬을 수행하는 것입니다. 수업 시간에 디스크를 이용한 정렬 기법인 2-way 병합 정렬을 다루었습니다. 테이프를 이용한 정렬의 경우 인접한 블록들이 저장된 위치에 따라 입, 출력 시간이 크게 차이가 납니다. 테이프를 이용한 정렬 방법들을 조사하여 각각에 대하여 설명해 보세요.

테이프를 이용한 정렬 방법은 주로 대규모 데이터의 정렬을 다룰 때 사용된다. 특히 테이프는 순차 접근 방식이기 때문에 저장된 데이터를 랜덤으로 접근하는 데 불리하지만, 대량의 데이터를 순차적으로 읽고 쓸 때는 효율적이다. 이런 특성 때문에 테이프를 활용한 정렬 기법은 외부 정렬에서 중요한 역할을 한다. 먼저, 테이프를 이용한 정렬의 기본적인 원리는 데이터를 블록 단위로 처리하는 것이다. 데이터는 큰 파일을 여러 개의 작은 블록으로 나누어 저장할 수 있으며, 이러한 블록은 테이프의 물리적 위치에 따라 순차적으로 저장된다. 정렬 과정에서 가장 기본적인 방법은 블록을 메모리로 읽어들여 일괄적으로 정렬한 후, 다시 테이프에 쓴다.…