자료구조의 이해 레포트2

소개

"자료구조의 이해 레포트2"에 대한 내용입니다.

목차

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

본문내용

1) 균형 병합 정렬(Balanced Merge Sort)
- 테이프에 저장되어 있는 데이터들을 주기억장치에 옮겨올 수 있도록 작은 블록으로 나눔
- 나뉘어진 블록들은 각각 주기억장치에서 정렬된 후에 다시 여러 개의 테이프에 분산되어 저장
- 나머지 과정이 순환적으로 반복되면서 블록의 수는 줄고 블록의 크기는 커지게 되며, 마지막으로 한 개의 블록만이 남게 되면 정렬이 완료됨
2) 계단식 병합 정렬(Cascade Merge Sort)
- 복사량을 줄이기 위한 불균형 방법의 다른 형태로, 연속 병합 정렬이라고도 함
- n개의 테이프가 주어졌을 때, 처음에는 (n-1)-원 병합을 수행하고, (n-2)-원 병합, …, 마지막으로 2-원 병합으로 반복적으로 수행하는 방법

참고자료

· 없음