외부 정렬 (External Sort)

외부 정렬(External Sort)이란?

데이터들의 크기가 주기억장치보다 커 정렬 할 데이터들을 주기억장치에 온전히 입력할 수 없는 경우 사용되는 정렬 방법을 의미한다. 예를 들어 주기억장치가 1GB고, 데이터 파일이 총 100GB라고 했을 때 내부 정렬 알고리즘을 사용하여 정렬할 수 없다.

 

외부 정렬 과정

분할

 

 

외부 정렬은 주기억장치에서 수용할 수 있는 데이터에 대해서만 읽어, 내부정렬을 수행 그 결과를 보조 기억 장치에 다시 저장한다. 여기서 내부 정렬은 상황에 맞는 정렬을 사용하면 된다. 

1. 메모리 만큼 데이터를 읽어온다. 
2. 활용할 내부 정렬을 이용하여 데이터를 정렬한다.
3. 정렬된 데이터를 보조 기억 장치에 기록한다.

정복

 

 

정렬되어 나눠진 블록들을 하나의 블록으로 만들기 위해 Merge 절차를 반복 수행해야 한다. 즉, 블록들을 부분적으로 주기억장치에 읽어 들여 Merge를 수행하여 보조 기억 장치에 다시 입력하는 과정을 반복한다.  2개의 블록들을 묶어 데이터를 일부분 읽어들이며  정렬을 수행한다. 1GB의 블록을 2개씩 짝지어 Merge 과정을 반복하면 2GB의 블록들이 만들어지며, 2GB의 블록들을 짝지어 Merge하는 과정을 반복하면 4GB의 블록들이 만들어진다. 이를 끝까지 반복하면 결국 하나의 블록이 남게 된다. 

while(블록 수가 1개가 될 때까지 반복한다.) { 
	1. 2개의 블록을 선택한다.
	2. 2개의 블록에서 메모리 크기에 맞게 데이터를 읽어온다. 
	3. 읽어온 데이터들을 각각 비교하며 합병 정렬의 정복 과정과 동일하게 진행하여 보조 기억 장치에 기록한다. 
	4. 2개의 블록에 존재하는 데이터가 완료됐으면 다음으로 2개의 블록을 선택한다. (만약, 블록이 1개 남았으면 그 블록은 그대로 보조기억장치에 기록한다. 
}

균형적 다방향 합병 정렬 

위의 예시처럼 외부 정렬 알고리즘은 합병 정렬을 응용/변형하여 만들 수 있다. 이를 균형적 다방향 합병 정렬이라고 한다. 

 

보조 기억 장치 접근 시간

외부 정렬 알고리즘은 정렬 시간보다는 아무래도 보조 기억 장치에 접근하는 시간을 최소화하는 것이 중요하다. 왜냐하면 정렬 과점에서 보조 기억 장치에 접근하는 횟수도 많고, 보조 기억 장치 접근 시간(access time)이 가장 오래걸리기 때문이다.

 

 

REFERENCE

https://dudri63.github.io/2019/02/03/algo32/

[Algorithm] 외부 정렬 (정렬)