[Algorithm] 외부정렬 (External Sort)

외부 정렬이란?

데이터들의 크기가 주기억장치보다 커 정렬할 데이터들을 주기억장치에 온전히 입력할 수 없는 경우 사용되는 정렬 방법을 의미한다.

예를 들어 주기억장치가 1GB고, 데이터 파일이 총 100GB라고 했을 때 내부 정렬 알고리즘을 사용하여 정렬할 수 없다.

 

Algorithm

1. 분할

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

내부 정렬은 상황에 맞는 정렬을 사용하면 된다.

이때 내부 정렬을 위해 

1. 메모리만큼 데이터를 읽어온다.

2. 활용할 내부 정렬을 이용하여 데이터를 정렬한다.

3. 정렬된 데이터를 보조 기억 장치에 기록한다.

 

2. 정복

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

이때, 병합된 블록을 run이라고 부른다.

while(블록 수가 2개 이상){
	2개의 블록을 선택
    	2개의 블록에서 메모리 크기에 맞게 데이터를 읽어온다.
    	읽어온 데이터들을 비교, merge sort의 정복 과정과 동일하게 진행하여 보조 기억 장치에 기록
}

 

3. 예시

분할 : 데이터를 2개로 분할한 후, 각각 내부 정렬

합병 : 각 분할된 데이터를 합병

50 110 95 10 100 36 153 40 120 60 70 130 22 140 80

1. 분할 1

- File 1 : (50 95 110)(40 120 153)(22 80 140)

- File 2 : (10 36 100)(60 70 130)

​

2. 합병 1

- File 3 : (10 36 50 95 100 110)(40 60 70 120 130 153)(22 80 140)

​

3. 분할 2

- File 1 : (10 36 50 95 100 110)(22 80 140)

- File 2 : (40 60 70 120 130 153)

- File 3 : 비었음

​

4. 합병 2

- File 3 : (10 36 40 50 60 70 95 100 110 120 130 153)(22 80 140)

​

5. 분할 3

- File 1 : (10 36 40 50 60 70 95 100 110 120 130 153)

- File 2 : (22 80 140)

- File 3 : 비었음

​

6. 합병 3

- File 3 : (10 22 36 40 50 60 70 80 95 100 110 120 130 140 153)

3. 균형적 다방향 합병 정렬

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

 

4. 보조 기억 장치 접근 시간

외부 정렬 알고리즘은 정렬 시간보다는 보조 기억 장치에 접근하는 시간을 최소화하는 것이 중요하다.

정렬 과정에서 보조 기억 장치에 접근하는 횟수가 많고, 접근하는 시간(access time)이 가장 오래 걸리기 때문이다.

 

 

ref {

https://ybdeveloper.tistory.com/118

https://blog.naver.com/PostView.nhn?blogId=jyk2367&logNo=222282293748&categoryNo=13&parentCategoryNo=0&viewDate=&currentPage=1&postListTopCurrentPage=1&from=search

}