• 정렬/합병의 개요
• 정렬 단계
• [1] 내부 정렬
• [2] 대체 선택
• [3] 자연 선택
• 런 생성 방법의 비교
• 파일 정렬/합병 방법의 차이점

정렬/합병의 개요

• 내부 정렬
  • 데이터가 적어서 메인 메모리 내에 모두 저장시켜 정렬가능할 때
• 외부 정렬
  • 데이터가 많아서 메인 메모리의 용량을 초과하여 보조 저장 장치에 저장된 파일을 정렬할 때
  • 레코드 판독, 기록에 걸리는 시간이 중요
  • 정렬/합병
    • 런(run) : 하나의 파일을 여러 서브파일로 나누어 내부 정렬 기법을 사용하여 정렬시킨 파일
    • 런을 합병하여 원하는 하나의 정렬된 파일을 만듬

정렬 단계

• 런 생성방법
  • 내부 정렬
  • 대체 선택
  • 자연 선택
  • 런의 수를 줄이기 위해 길이는 길게
    그래야 합병할 때 런의 수가 적어 빠른 시간내 처리 가능

[1] 내부 정렬

• 런 생성 방법
  • 파일을 n개 레코드씩 분할
  • 분할된 레코드들을 내부 정렬 기법으로 정렬
  • 길이를 고정
• 특징
  • 제일 마지막 런을 제외하고 모두 길이가 같다.

[2] 대체 선택

• 런 생성 방법

• 특징
  • 내부 정렬과 달리 입력 파일의 일부 정렬된 레코드들의 순서를 이용
  • 내부 정렬을 이용한 경우보다 런의 길이가 길다.
    • 런의 개수가 줄어(↓) –> 합병 과정 비용 줄임(↓)
  • 런의 평균 예상 길이 : 2m
  • 내림차순일 때 최악
  • 오름차순일 때 런 1개 생성
  • 내부에 비해 런의 수는 1/2배, 런의 길이는 2배

[3] 자연 선택

• 런 생성 방법
  • 대체 선택과는 달리 동결된 레코드들을 버퍼에 유지하지 않고
    보조 저장 장치에 예비 장소를 설정하여 별도 저장
  • 하나의 런은 예비장소가 꽉 차고 버퍼에 들어올 데이터가 없거나 입력 파일이 공백이 될 때까지 계속 생성
• 특징
  • 대체 선택보다 런을 길게하여 런 수를 줄임(↓)
    –> 합병과정 비용을 줄임(↓)

런 생성 방법의 비교

• 내부 정렬
  • 마지막 럭을 제외하고 모든 런들의 길이가 같음
  • 런의 길이를 예측할 수 있으므로 합병 알고리즘이 간단
• 대체 선택
  • 내부 정렬보다 평균적으로 훨씬 긴 런을 생성
  • 런의 길이가 길수록 합병 비용이 적음
  • 런의 길이가 일정치 않아 정렬/합병 알고리즘이 복잡
• 자연 선택
  • 앞의 두 방법보다 더 긴 런을 생성할 수 있음
  • 예비 장소로의 입출력이 문제가 됨
  • 긴 런 생성에 따른 효율화가 예비 장소 전송 비용보다 이익이 될 수도 있음

파일 정렬/합병 방법의 차이점

• 차이점을 나타내는 매개 변수
  • 적용하는 내부 정렬 방식
  • 내부정렬을 위해 할당된 메인 메모리의 크기
  • 정렬된 런들의 보조 저장 장치에서의 저장 분포
  • 정렬/합병 단계에서 동시에 처리할 수 있는 런의 수
• 정렬/합병 기법의 성능
  • 매개 변수에 따라 런의 수와 합병의 패스(pass)수 결정
    • 패스 수 : 정렬/합병 기법이 몇 번의 반복적 수행을 거쳐서 최종 파일에 출력하느냐를 나타내는 것
  • 레코드 판독/기록 횟수 성능에 영향을 미치는 요인
    • 가능한 런의 길이를 길게 만들어 런의 수를 최소화
    • 동시에 합병할 수 있는 런의 수를 늘리면 합병의 패스 수는 감소