[자료구조] 정렬 2 (외부 정렬 - 합병 정렬)

외부 정렬

정렬하려는 리스트 전체가 컴퓨터의 메인 메모리에 모두 올라갈 수 없다면 내부 정렬 사용 불가

 

블록 - 한 번에 디스크로부터 읽거나 디스크에 쓸 수 있는 데이터 단위, 여러 개의 레코드들로 구성

 

판독/기록 시간에 영향을 미치는 요소

• 탐구 시간: 판독/기록 헤드가 디스크 상의 원하는 실린더로 이동하는데 걸리는 시간, 헤드가 가로질러야 하는 실린더 수에 따라 결정됨
• 회전지연 시간: 트랙의 해당 섹터가 판독/기록 헤드 밑으로 회전해 올 때까지 걸리는 시간
• 전송 시간: 디스크로 오는 디스크로부터 데이터 블록을 전송하는 데 걸리는 시간

 

합병 정렬

1. 입력 리스트의 여러 세그먼트들을 좋은 내부 정렬 방법으로 정렬
   런(run) - 정렬된 세그먼트들
   런이 생성되면 외부 저장 장치에 기록됨
2. 1에서 만들어진 런들은 하나의 런이 될 때까지 합병 트리 형식을 따라 합병

 

예시

조건

- 입력 리스트는 디스크에 저장되어 있고 250 레코드의 블록 길이를 가지고 있음

- 작업 공간으로 사용할 또 다른 디스크를 갖고 있음

 

1. 런 내부 정렬

• 내부적으로 한 번에 3개의 블록(750개의 레코드)을 정렬해서 6개의 런 R1-R6을 만들고, 이 런들은 작업 디스크에 수록

내부 정렬 후 얻어진 블록화 된 런 (한 런당 세 블록)

 

2. 런 합병

• 내부 메모리에 250개의 레코드를 수용할 수 있는 3개의 블록을 마련
• 2개의 블록은 입력 버퍼로 사용, 하나는 출력 버퍼로 사용
• 입력 버퍼로 각 런으로부터 블록 하나씩 읽어 들임
• 런의 블록들은 입력 버퍼에서 출력 버퍼로 합병
• 출력 버퍼가 다 차면 디스크에 기록
• 입력 버퍼가 공백이 되면 같은 런에서 다음 블록을 읽어 들여 다시 채움

 

6개 런의 합병

 

시간복잡도

표기법

• $t_s$ - 최대 탐구 시간
• $t_l$ - 최대 회전 지연 시간
• $t_{rw}$ - 250개의 레코드로 구성된 한 블록을 읽거나 쓰는데 걸리는 시간
• $t_{IO}$ - 한 블록을 입력 또는 출력하는데 걸리는 시간 = $t_s+t_l+t_{rw}$
• $t_S$ - 750개의 레코드를 내부적으로 정렬하는 시간
• $n{t}_m$ - 입력 버퍼에서 출력 버퍼로 n개의 레코드를 합병하는데 걸리는 시간

 

1. 18블록의 입력 판독: $18t_{IO}$
   내부 정렬: $6t_{IS}$
   18블록 기록: $18t_{IO}$
   → $36t_{IO}+6t_{IS}$
2. 1-6런을 쌍으로 합병
   → $36t_{IO}+4500t_m$
3. 두 개의 1500 레코드로 된 런을 합병(12블록)
   → $24t_{IO}+3000t_m$
4. 3000 레코드의 런과 1500 레코드의 런을 합병
   → $36t_{IO}+4500t_m$

 

전체 시간 = $132t_{IO}+12000t+m+6t_{IS}$

 

k-원 합병

m개의 런이 있을 때의 합병 트리

• ⌈$lo{g}_{2}m$⌉ + 1의 레벨을 가짐
• 총 ⌈$lo{g}_{2}m$⌉ 패스 필요 → 고차 합병을 사용해서 줄일 수 있음

 

16개의 런에 대한 4-원 합병