← 질문 목록
#373깊이 0
외부 정렬 알고리즘에서 대체 선택 정렬을 사용하는 이유는 무엇인가?
자료구조 · 알고리즘
초기 런의 평균 길이를 메모리 크기의 두 배로 늘려 디스크 병합 횟수를 줄이기 때문이다.
| 방식 | 런 생성 길이 | 특징 |
|---|---|---|
| 일반 정렬 | 메모리 크기 (N) | 메모리가 차면 정렬 후 디스크에 쓴다 |
| 대체 선택 정렬 | 평균 2N | 방금 출력한 값보다 큰 값을 계속 덧붙인다 |
대체 선택 정렬은 메모리 크기보다 훨씬 긴 런을 만든다.
우선순위 큐에 메모리 크기만큼 데이터를 채운다. 가장 작은 값을 꺼내 디스크에 쓰고 새 데이터를 읽는다. 새 값이 방금 쓴 값보다 크면 현재 런에 포함한다.
무작위 데이터가 들어오면 평균적으로 메모리 크기의 두 배에 달하는 런이 완성된다. 런의 수가 줄어들수록 디스크 I/O를 수반하는 병합 단계가 줄어든다.
이미 정렬된 데이터가 들어오면 단 하나의 런으로 정렬을 마친다. 반면 역순 데이터가 들어오면 런의 길이는 메모리 크기와 같아진다.