[은행 필기대비 자료구조-05] 정렬 알고리즘_3

외부정렬

 

1> 외부 정렬은 데이터의 크기가 주기억장치의 용량보다 클 경우에 디스크 등의 외부 보조기억장치에 데이터의 대부분을 저장

 

==> 병합 정렬이 대표적

 

2> 보조기억장치에 입력을 저장 상태에서 수행되는 외부 정렬 ==> 입력을 분할해 주기억장치에서 수용할 수 있는 만큼의 데이터에 대해서만 내부 정렬 수행

 

 

 

EX) [31 , 20 ,22 ,30 ,35 ,23 ,25 ,32]

 

1> 분할: [31 ,20 ,22 ,30] // [35 , 23 ,25 ,32]

 

2>분할: [31,20] [22,30] ,[35,23] ,[25,32]

 

3> 분할:[31] , [20] , [22] , [30] , [35], [23] , [25] , [32]

 

4> 정복,결합(재귀호출) : [20 , 31] , [22, 30] , [23,35] , [25,32]

 

5> 정복,결합(재귀호출) : [20,22,30,31] , [23,25,32,35]

 

6> 정복,결합(재귀호출) : [20,22,23,25,30,31,32,35]