자료구조론[외부정렬]

등록일 2003.07.01 한글 (hwp) | 5페이지 | 가격 500원

목차

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

본문내용

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

① 2-원 병합 정렬(2-way Merge Sort)
외부 정렬을 수행할 때 가장 많이 사용되는 정렬 방식이다. 정렬은 다음과 같이 진행된다.
ⓐ 입력 파일의 일부를 주기억 장치에 적재한 후 내부 정렬을 수행한다.
ⓑ 이렇게 정렬된 부파일을 런(run)이라 하며 외부 기억 장치에 하나의 파 일로 저장한다.
ⓒ 이렇게 만들어진 여러 개의 런을 병합 정렬을 이용하여 런을 2개씩 병합하여 하나의 런이 될 때까지 수행한다.
      최근 구매한 회원 학교정보 보기
      1. 최근 2주간 다운받은 회원수와 학교정보이며
         구매한 본인의 구매정보도 함께 표시됩니다.
      2. 매시 정각마다 업데이트 됩니다. (02:00 ~ 21:00)
      3. 구매자의 학교정보가 없는 경우 기타로 표시됩니다.
      최근 본 자료더보기
      추천도서