자료구조론[외부정렬]

목차

1.디스크를 이용한 정렬
2. 테이프 정렬(Tape sort)

본문내용

정렬하려는 파일의 크기가 너무 커서 주기억장치에 적재할 수 없어 보조기억 장치인 디스크나 테이프를 이용하여 정렬을 수행한다. 외부 정렬의 단계는 우선 주기억장치에 적재 가능한 크기로 여러 개의 부파일로 나눈다. 그 다음 나누어진 각 부파일을 내부 정렬 알고리즘으로 정렬한 후 다시 보조 기억 장치에 저장하고 정렬된 여러 개의 부파일을 다시 하나의 파일로 병합 정렬하여 정렬을 완료한다.
1.디스크를 이용한 정렬
보조 기억 장치인 디스크는 직접 접근(direct access)이 가능한 장치로 각 부파일을 병합하여 읽거나 쓰는 위치는 크게 중요하지 않다 또한 입출력 버퍼(buffer)로 사용할 수 있는 주기억 장치의 여유만 있으면 여러 개의 부파일을 동시에 병합한다.

① 2-원 병합 정렬(2-way Merge Sort)
외부 정렬을 수행할 때 가장 많이 사용되는 정렬 방식이다. 정렬은 다음과 같이 진행된다.
ⓐ 입력 파일의 일부를 주기억 장치에 적재한 후 내부 정렬을 수행한다.
ⓑ 이렇게 정렬된 부파일을 런(run)이라 하며 외부 기억 장치에 하나의 파 일로 저장한다.
ⓒ 이렇게 만들어진 여러 개의 런을 병합 정렬을 이용하여 런을 2개씩 병합하여 하나의 런이 될 때까지 수행한다.

참고 자료

없음