정렬(외부정렬 - External Sort)

이번 시간에 포스팅할 내용은 외부 정렬입니다. 외부 정렬은 대용량의 보조 기억 장치를 사용해서 정렬하는 것으로 디스크를 이용한 병합 방식(2-way병합, n-way 병합), 테이프를 이용한 균형 병합 정렬, 계단식 병합 정렬, 다단계 병합 정렬, 교대식 병합 정렬 등이 있습니다. 각 종류에 대하여 간단하게 설명하도록 하겠습니다. 단, 2-way병합이나 n-way병합은 내부 정렬의 병합방법을 참조하시기 바랍니다.

 

균형병합정렬이란 n개의 테이프 장치가 주어지면 각 테이프에는 똑같은 크기의 레코드들이 작은 블록으로 나누어 내부 방법을 통해 정렬합니다. 나누어진 블록들은 각각 주기억 장치에서 정렬된 후에 다시 여러 개의 테이프에 분산되어 저장되는데 나머지 과정이 순환적으로 반복되면서 블록의 수는 줄고 블록의 크기는 커지게 됩니다. 마지막으로 한 개의 블록만이 남게되면 정렬이 완료되는 방법입니다.

 

계단식 병합정렬이란 부분적으로 정렬된 서브파일들을 한 개의 빈 테이프에 병합해 정렬하는 방법을 반복하여 정렬하는 방법입니다. 연속병합정렬이라고도 불리는데 n개의 테이프가 주어졌을 때, 처음에는 (n-1)-way병합을 수해하고, (n-2)-way병합, … 2-way병합 정렬을 반복적으로 수행하는 방법을 통해 정렬이 완료디는 방법입니다.

 

교대 병합정렬은 테이프의 읽기 쓰기 기능이 역방향과 순방향이 다 가능한 테이프 장치의 기능을 이용하여 정렬하는 방법입니다. n개의 테이프가 주어졌을 때, 테이프 하나는 정렬되지 않은 입력 파일이 저장되어 있고, 비어있는 n-1개의 테이프를 이용하여 병합 정렬하여 정렬이 완료되는 방법입니다.

 

다단계 합병정렬은 분산수록되는 레코드의 수를 피보나치 수열을 이용하여 레코드를 분산수록하여 정렬하는 방법입니다. n개의 입력 파일과 1개의 출력 파일로 구성되어 입/출력 파일 수가 같지 않는 불균형 합병이 이루어집니다. 초기 입력 파일에 대한 분배가 복잡하다는 특징이 있습니다.

 

외부 정렬에 대하여는 간단하게 설명하고 넘어가지만 외부 정렬 또한 내부정렬에서 사용한 방법을 사용한다는 점과 데이터가 많아 주기억장치에서 모두 처리할 수 없다는 것을 이해하시면 될 것 같습니다.

 

다음 포스팅부터는 자료구조2의 세부 정렬의 내용이 아닌, 자료구조3을 설명하도록 하겠습니다.