[파일처리] 문제03

문제03

입력 데이터가 다음 순서와 같이 들어올 때, 자연선택을 이용해서 런을 만들려고 한다. 첫 번째 런 생성부터 두 번 째 런의 두 번째 데이터가 출력될 때까지 런이 생성되는 과정을 설명하시오. 단, 버퍼 크기와 예비 장소 크기는 모두 3으로 가정한다.

[ 32, 4, 24, 15, 9, 20, 17, 2, 48, 49, 8, 59, 1, 11 ]

풀이) 런이 생성되는 과정(두번째 런의 두번째 데이터가 출력될 때까지)

1. 런1생성, 버퍼에 입력데이터 32, 4, 24 불러옴
2. 버퍼에서 제일 작은 4 출력 (런1)
3. 입력데이터 15는 4보다 크므로 버퍼의 빈 자리(이전 4자리)에 입력데이터 15 불러옴
4. 버퍼에서 제일 작은 15 출력 (런1)
5. 입력데이터 9는 15보다 작으므로 예비저장소로 이동
6. 입력데이터 20은 15보다 크므로 버퍼의 빈 자리(이전 15자리)에 20 불러옴
7. 버퍼에서 제일 작은 20 출력 (런1)
8. 입력데이터 17은 20보다 작으므로 예비저장소로 이동
9. 입력데이터 2는 20보다 작으므로 예비저장소로 이동
10. 입력데이터 48은 20보다 크므로 버퍼의 빈 자리(이전 20자리)에 48 불러옴
11. 버퍼에서 제일 작은 24 출력 (런1)
12. 입력데이터 49는 24보다 크므로 버퍼의 빈 자리(이전 24자리)에 49 불러옴
13. 버퍼에서 제일 작은 32 출력 (런1)
14. 입력데이터 8은 32보다 작으므로 예비저장소로 이동해야하나,
    예비저장소가 동결되어있어 다시 입력데이터로 이동
15. 버퍼에 저장된 48, 48 출력 (런1), 런1 종료
16. 런2 생성, 버퍼에 예비저장소에 저장된 9, 17, 2 불러옴
17. 버퍼에서 제일 작은 2 출력 (런2)
18. 입력데이터 8는 2보다 크므로 버퍼의 빈 자리(이전 2자리)에 입력데이터 8 불러옴
19. 버퍼에서 제일 작은 8출력 (런2)