<Algorithm> External Sort ① MergeSort

HONG CHANGSUB -

본 게시물은 영남대학교 조행래 교수님의 강의를 기반으로 작성되었습니다.

1. Binary Merge Sort

  • 주 기억장치의 크기를 넘어서는 파일을 다룰 때 보조기억장치의 도움을 받아 데이터를 정렬하는 알고리즘이다.-> 외부정렬의 개념
  • 쉽게 보면 DRAM의 크기보다 큰 데이터를 가진 파일을 정렬해야하는 상황에서 SSD나 HDD의 도움을 받아서 정렬을 한다고 이해하면 쉽다.
  • 외부 정렬시 Run이라는 개념이 도입되는데, 이는 정렬할 파일을 몇개의 그룹으로 나눌때 나눠진 그룹을 일컫는 하나의 단위라고 보면된다. 즉, 주기억장치에 적재가 가능한 사이즈여야 한다.
  • Run의 크기의 경우 통상적으로는 momory의 크기보다 작다.
  • 기본적으로 merge-sort 방식을 따라서 정렬한다.
  • 각 run에 대해 내부정렬 후 다른 파일에 저장한다.
  • 병합된 run의 수가 1이 될때까지 병합을 반복한다.(가장 큰 덩어리가 될 때까지)
  • Run의 개수와 Run의 크기는 서로 다른 값이 될수 있다.
외부정렬 기본 개념!

2. Binary Merge Sort

  • Sorting Phase와 Merging Phase로 나뉜다.
  • 초기 run들을 정렬 한 뒤, 2개의 외부 파일에 저장하는 방식
  • 초기 run의 수가 R이면,Level의 수 = [log2R] + 1
  • 전체 병합 단계의 수 : [log2R]
  • 여러번의 재분배가 필요해서 성능이 좋진 않다
  • Input File(Run=3, 메모리의 크기가 데이터 3개까지 저장가능)
    • (50,110,95) (10,100,36) (153,40,120) (60,70,130) (22,140,80)
  • Sorting Phase 완료후
    • File1 : (50,95,110) (40 120 153) (22 80 140)
    • File2 : (10 36 100) (60 70 130)
  • 첫 번째 병합 결과:
    • File3 : (10 36 50 95 100 110) (40 60 70 120 130 153) (22 80 140)
  • 재분배 결과 :
    • File1 : (10 35 50 95 100 110) (22 80 140)
    • Fiel2 : (40 60 70 120 130 153)
    • File3 : 비어있음
  • 두번째 병합 결과:
    • File3 : (10 35 40 50 60 70 95 100 110 120 130 153) (22 80 140)
  • 다시 재분배... :
    • File1 : (10 35 40 50 60 70 95 100 110 120 130 153)
    • File2 : (22 80 140)
    • File3 : 비어있음
  • 세번째 병합!! :
    • File3 : (10 22 35 40 50 60 70 80 95 100 110 120 130 140 153)

3. Balanced Binary Merge Sort

  • Output file의 수 = Input file의 수(바이너리니까 각각 2개!)
  • Iuput file : (50,110,95) (10,100,36) (153,40,120) (60,70,130) (22,140,80)
  • Sorting Phase의 완료 후 :
    • File1 : (50,95,110) (40 120 153) (22 80 140)
    • File2 : (10 36 100) (60 70 130)
  • 첫 번째 병합 결과
    • File3 : (10 36 50 95 100 110), (22 80 140)
    • File4 : (40 60 70 120 130 153)
  • 두 번째 병합 결과
    • File1 : (10 36 40 50 60 70 95 100 110 120 130 153)
    • File2 : (22 80 140)
  • 세 번째 병합 결과
    • File3 : (10 22 35 40 50 60 70 80 95 100 110 120 130 140 153)

4. Balanced k-way Merge Sort(k > 2)

  • k개의 수만큼 input과 output 파일의 수를 설정!
    • Run의 개수가 N인 경우,[logkN]만큼의 병합단계의 수를 가진다!
    • K의 값은 아무리 커도 메모리의 크기보다 클 수는없다.
    • Input file : (50,110,95) (10,100,36) (153,40,120) (60,70,130) (22,140,80)
    • Soting Phase 완료후 :
      • File 1 : (50 95 110) (60 70 130)
      • File 2 : (10 36 100) (22 80 140)
      • File 3 : (40 120 153)
    • 첫번째 병합의 결과 :
      • File 4 : (10 36 40 50 95 100 110 120 153)
      • File 5 : (22 60 70 80 130 140)
      • File 6 : 비어있음
    • 두번째 병합의 결과 :
      • File 1 : (10 22 35 40 50 60 70 80 95 100 110 120 130 140 153)

5. Polyphase Merge Sort

  • 빈 파일을 output으로 사용하여 공간을 효율성 증가!
  • Iuput file : (50,110,95) (10,100,36) (153,40,120) (60,70,130) (22,140,80)
  • Sorintg Phase 완료 후 :
    * File1 : (50,95,110) (40 120 153) (22 80 140)
    * File2 : (10 36 100) (60 70 130)
  • 첫번째 병합의 결과 :
    * File1 : (22 80 140)
    * File2 : 비었음
    * File3 : (10 36 50 95 100 110) (40 60 70 120 130 153)
  • 두번째 병합 결과 :
    * File1 : 비었음
    * File2 : (10 22 36 50 80 95 100 110 140)
    * File3 : (40 60 70 120 130 153)
  • 세번째 병합 결과 :
    * File1 : (10 22 40 36 50 60 70 80 95 100 110 120 130 140 153)