[자료구조, Algorithm] 외부정렬(External Sort) HWP version

소개

자료구조의 정렬중에서 외부정렬에 대한 내용을 심도있게 정리하였습니다.

목차

1. 외부정렬 개요
1.1 외부정렬의 개념
1.2 내부정렬의 문제점
1.3 외부정렬 알고리즘
2. 합병정렬
2.1 합병
2.2 합병 정렬
2.3 리스트 합병 정렬
2.4 상향식 합병 정렬
2.5 활용도 특징
2.6 최적화된 구현
2.7 재 방문된 재귀
3. 외부정렬 종류 및 분석
3.1 자연 2-원 합병
3.2 균형 2-원 합병
3.3 균형 m-원 합병
3.4 다단계 합병
3.5 대체 선택에 의한 런 생성
4. 알고리즘 구현 및 성능 비교
5. 결론
6. 참고 문헌

본문내용

1. 외부정렬 개요

1.1 외부정렬의 개념
많은 중요한 정렬 응용은 매우 큰 파일들을 처리해야 하므로 해서, 그 크기가 너무커서 컴퓨터의 주 기억장소에 적합하지 않을 정도이다. 그런 응용에 대한 적절한 방법은 중앙 처리 장치에 대한 외부적으로 처리하는 큰 양을 지니므로해서 외부 방법이라고 부른다.(지금까지 살펴본 내부 방법들과 반대되는 개념)
외부 알고리즘을 지금까지 본 것과 아주 다른 두 가지 중요한 요소가 있다. 첫째, 항목을 접근하는 비용은 어떤 장부나 계산 비용보다 더 큰 정도의 순서이다. 둘째, 이같은 높은 비용 이상으로 이용된 외부 기억장치에 따라서 접근에는 심각한 제약이 있다. 예를 들면, 자기 테이프상에 항목을들 순차적인 방법으로서만 접근된다.
외부 기억장치 종류와 비용들의 많은 다양성은 현재 기술에 매우 의존적인 외부 정렬 방법들로 만든다. 이같은 방법들은 복잡하고 그리고 많은 파라미터들이 그것의 활용도에 영향을 준다. 즉, 기술적으로 간단한 변경 때문에 좋은 방법으로 평가되지 않고 사용되지 않는다는 것은 외부 정렬에서 명백히 가능하다. 이같은 이유에 대해, 본 장에서는 특별한 구현을 개발하기 보다는 오히려 일반적인 방법들에 중점을 둔다.
간단히 외부 정렬에 대해, 문제의 “시스템”면은 확실히 “알고리즘”면과 같이 중요하다. 양쪽 영역은 효과적인 외부 정렬이 개발되어지는 경우에 조심스럽게 고려가 되어야 한다. 외부 정렬에서의 주된 비용은 입력과 출력이다. 어떤 사람이 매우 큰 파일을 정렬하기 위해서 효율적인 프로그램을 구현하려고 하는 좋은 연습은 먼저 큰 파일을 복사하기 위해서 효율적인 프로그램을 구현하는 것이고, 그때(만약 그것이 매우 쉬는 경우) 큰 파일에서 요소들의 순서를 거꾸로 하도록 효율적인 프로그램을 구현하는 것이다. 이같은 문제들을 효율적으로 풀기 위해서 제기되는 시스템 문제들은 외부 정렬에서 제기 되는 것들과 비슷하다. 어떤 비사소한 방법으로서 큰 외부 파일을 순열화 시키는 것이 비록 키들 비교는 없는 것이지만 그것을 정렬하는 것과 같은 정도로 어렵다. 외부 정렬에서, 외부 기억장치와 주 기억장치 사이에 데이터의 각 조각이 이동되는 수를 제한하고, 그런 변형이 이용가능한 하드웨어에 의해 효율적으로 수행이 되는 것이 관심사이다.

참고자료

· ▷ ‘황종선, 정영식 공저’
· C언어로 설명한 알고리즘, 정익사
· ▷ ‘황종성, 손진곤 공저’
· Java 언어로 설명한 자료구조론,
· 정익사
· ▷ ‘이재규 지음’
· C언어로 배우는 알고리즘,
· 세화 출판사
· ▷ ‘전문석 역’
· 컴퓨터 알고리즘, 홍릉과학원
· ▷ ‘민용식, 오삼권 역’
· C++ 알고리즘, 대영사