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

소개글

[자료구조, 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. 참고 문헌

본문내용

hile (runs>1);
return( unit );
};
③polyphase merge sort
Polyphase merge sort
sort()
{
int i, j, some;
extern int maxfiles, maxruns[], actruns[];
extern struct rec LastRec[];
/*** Initialize input/output files ***/
OpenRead( 1 );
for (i=2; i<=maxfiles; I++) OpenWrite( i );
/*** Initialize maximum and actual count of runs ***/
for (i=0; i<=maxfiles; I++) maxruns[i]=actruns[i]=0;
maxruns[0] = maxruns[maxfiles] = 1;
distribute();
/*** Initialize merging phase ***/
for (i=2; i<=maxfiles; i++)
{ OpenRead( i ); LastRec[i] = ReadFile(i); }
for (i=1; maxruns[0]>1; i = (i%maxfiles)+1 ) {
OpenWrite( i );
while ( maxruns[ (i%maxfiles)+1 ] > 0 ) {
for (j=1; j<=maxfiles; j++)
if ( j!=i ) {
if ( maxruns[j]>actruns[j] )
FilStat[j] = \'-\';
else { FilStat[j] = \'i\';
actruns[j]--;
some = TRUE;
}
maxruns[j]--;maxruns[0]--;
}
maxruns[i]++; maxruns[0]++;
if (some) { merge(i); actruns[i]++; }
}
OpenRead( i ); LastRec[i] = ReadFile(i);
};
return( i==1 ? maxfiles : i-1 );
};
4.4 성능비교
성능비교를 하기 위해 내부정렬은 쉘 정렬을 사용하였다. 그 이유는 많은 데이터를 비교적 빨리 정렬할 수 있고 메모리를 많이 차지하지 않기 때문이었다.
성능을 비교하기 위해 사용된 외부정렬 알고리즘은 natural 2-way merge sort, natural 3-way merge sort, balanced 2-way merge sort, balanced 3-way merge sort, polyphase 3-way merge sort 였다.
입력으로 사용된 데이터는 랜덤으로 발생시킨 양의 정수를 파일에 담아서 사용하였다. external sort는 외부에서 데이터를 불러오는 것이기에, 이를 구현하기 위해 파일에서 입력을 받았다.
정렬하는 기준은 생성되는 run의 수를 기준으로 하였는데 10,30,50,70,90,110개의 run으로 나누어 test를 실시하였다.
test는 총 10번 실시하여 그 평균을 내었다. 각 실시 횟수에 따른 데이터는 다음 장에 있다. 측정시간은 tick으로서 ms이다.
밑의 표와 데이터는 위의 테스트 결과를 표와 그래프로 나타낸 것이다.
결론적으로 polyphase merge sort가 가장 성능이 좋은 것으로 나타났다.
run No.
sort
10
30
50
70
90
110
Natural-2
0.2
0.6
1
1.5
2.4
3.2
Natural-3
0.1
0.4
0.6
1
1.6
2.3
Balanced-2
0.1
0.3
0.55
1.2
1.3
1.8
Balanced-3
0.1
0.25
0.4
0.6
1
1.3
Polyphase-3
0.1
0.2
0.2
0.5
0.6
0.7
run의 수가 증가할수록 polyphase merge sort의 성능이 더 잘 발휘됨을 알 수 있었다.
natural merge sort는 전체적으로 run의 수가 증가할수록 성능이 떨어진다. 이는 합병을 할 때, 사용되는 파일의 수가 증가하는 경우 성능이 좋은 것으로 나타났다.
사용되는 파일의 수에 따른 성능의 차이는 natural 2-way merge sort와 natural 3-way merge sort, balanced 2-way merge sort와 balanced 3-way merge sort의 결과에서 알 수 있다.
정리를 하자면, 데이터의 입/출력되는 속도가 일정하다고 할 때, run의 수와 사용하는 파일의 수에 따라 알고리즘의 성능이 좌우된다고 볼 수 있다.
5. 결론
많은 현대 컴퓨터 시스템은 매우 큰 파일들을 정렬하는 방법을 구현함에 있어 간과하지 않는 큰 가상 기억 장치 능력을 제공한다. 좋은 가상 기억 장치 시스템에서, 프로그래머는 데이터가 필요할 때 외부에서 내부 기억장소에 전송하는 것은 시스템의 책임을 남겨두고서 데이터의 많은 양을 나타낸다. 이같은 방법은 많은 프로그램이 상대적으로 적은 “참조의 국지성(locality of reference)”를 지닌다는 사실에 의존된다. 즉, 기억 장소에 각 참조는 다른 최근의 참조된 영역에 상대적으로 근접된 기억장소의 영역이다. 이것은 외부에서 내부 기억장소로의 전송이 일어나는 것을 의미한다. 적은 참조의 국지성으로 된 내부 정렬 방법은 기억 장소 시스템에서 매우 잘 처리가 된다.(예를 들면, 퀵 정렬은 두 개의 “국지성”을 지닌다. 즉, 대부분의 참조는 2개의 분할된 포인터중 하나에 근접된 것이다) 그러나 의미 있는 보관에 대해 시스템 프로그래머가 체크하다. 즉, 어느 경우에서든 참조의 국지성을 지니지 않은 기수 정렬과 같은 방법은 가상 기억장치 시스템에서 그리고 비록 이용이 가능한 가상 기억 장치 시스템이 얼마나 잘 구현이 되는 가에 따라서 퀵 정렬이 문제가 되는 것이다. 다른 한편으로 디스크 파일을 정렬하는 단순한 내부 정렬 방법의 전략은 좋은 가상 기억장치 환경에서 심각한 고려를 해야 한다.
6. 참고 문헌
▷ ‘황종선, 정영식 공저’
C언어로 설명한 알고리즘, 정익사
▷ ‘황종성, 손진곤 공저’
Java 언어로 설명한 자료구조론,
정익사
▷ ‘이재규 지음’
C언어로 배우는 알고리즘,
세화 출판사
▷ ‘전문석 역’
컴퓨터 알고리즘, 홍릉과학원
▷ ‘민용식, 오삼권 역’
C++ 알고리즘, 대영사

키워드

자료구조,   Algorithm,   외부정렬,   External Sort,   HWP