[Algorithm] 정렬 알고리즘 : 외부 정렬

이전에 버블, 선택, 삽입, 합병 등 여러 정렬알고리즘에 대해서 많은 게시글을 올렸었다.

 

정렬알고리즘의 종류로는 내부정렬, 외부정렬이 있다.

 

내부정렬

• 입력의 크기가 주기억 장치의 공간보다 크지 않는 경우에 수행되는 정렬이다.
• 버블, 선택, 삽입, 합병, 쉘, 힙, 합병, 퀵정렬 등

---

외부정렬

• 입력의 크기가 주기억 장치 공간보다 큰 경우, 보조기억 장치에 데이터를 저장하여 정렬을 하고자 하는 경우에 사용된다.
• 보조 기억 장치에 있는 입력을 여러 번에 나누어 주기억 장치에 읽어들인 후, 정렬하여 보조 기억 장치에 다시 저장하는 과정을 반복한다.
• 예를 들면, 주기억 장치의 용량이 1GB이고, 입력 크기가 100GB라면, 어떤 내부 정렬 알고리즘으로도 직접 정렬할 수 없어서 외부 정렬알고리즘을 사용해야한다.

 

1️⃣ 외부 정렬 방법

1. 입력을 분할하여 주기억 장치에 수용할 만큼의 데이터에 대해서만 내부정렬을 수행하고,
2. 그 결과를 보조 기억 장치에 일단 다시 저장한다.

• 즉, 100GB의 데이터를 1GB 만큼씩 주기억 장치로 (100번) 읽어 들이고, 퀵 정렬과 같은 내부정렬 알고리즘을 통해 정렬한 후, 다른 보조 기억 장치에 저장한다.
• 이를 반복하면, 원래의 입력이 100개의 정렬된 블록으로 분할되어 보조 기억 장치에 저장된다. 

  

• 그 다음 과정은 정렬된 블록들을 하나의 정렬된 거대한 (100GB 크기의)블록으로 만드는 것이다.
  • 이 과정은 반복적인 합병 (merge)을 통해서 이루어진다. 즉, 블록들을 부분적으로 주기억 장치에 읽어 들여서, 합병을 수행하여 부분적으로 보조 기억 장치에 쓰는 과정이 반복된다.

    

    1GB 블록 2개가 2GB 블록 1개로 합병되는 과정

  • 나머지 98개의 블록에 대해서 위와 같이 49회를 반복하면, 2GB 블록이 총 50개 만들어 진다.
  • 그 다음엔 2GB 블록 2개씩 짝을 지어 합병시키는 과정을 총 25회 수행하면, 4GB 블록 25개가 만들어진다.
  • 이러한 방식으로 계속 합병을 진행하면, 블록 크기가 2배로 커지고 블록의 수는 1/2로 줄어들게 되어 결국에는 100GB 블록 1개만 남는다.

 

외부 정렬 알고리즘은 보조 기억 장치에서의 읽고 쓰기를 최소화하는 것이 매우 중요하다.
- 왜냐하면 보조 기억 장치의 접근 시간이 주기억 장치의 접근 시간보다 매우 오래 걸리기 때문이다.

 

 

2️⃣ 외부 정렬 알고리즘 (ExternalSort) : 의사 코드

• 주기억 장치 용량 : M
• 외부정렬 알고리즘은 입력이 저장된 보조 기억 장치 외에 별도의 보조 기억 장치를 사용한다.
• 보조기억 장치 : HDD (2개 활용!)
• 입력 : 입력 데이터 저장된 입력 HDD
• 출력 : 정렬된 데이터가 저장된 출력 HDD

  입력 HDD에 저장된 입력의 크기가 M만큼씩 주기억 장치에 읽어 들인 후, 내부 정렬 알고리즘으로 정렬하여 별도의 HDD에 저장한다.
  다음의 단계에서 별도의 HDD는 입력 HDD로 사용되고, 입력 HDD는 출력 HDD로 사용된다.
  
  while( 입력 HDD에 저장된 블록 수 > 1 )
  {
    입력 HDD에 저장된 블록을 2개씩 선택하여, 각 블록의 데이터를 부분적으로 주기억 장치에 읽어들여서 합병을 수행한다.
    이때 합병된 결과는 출력 HDD에 저장한다. 
    단, 입력 HDD에 저장된 블록 수가 홀수일때는 마지막 블록은 그대로 출력 HDD에 저장한다.
    
    입력과 출력 HDD의 역할을 바꾼다.
  }
  
  return 출력 HDD​

  • 입력의 크기가 N이라면, N/M개의 블록이 만들어진다. 단, 편의상 N이 M의 배수라고 가정하자.
  • 첫 합병이 수행되면 각각의 블록의 크기는 2M이 된다. 그다음 4M -> 즉, 2배가 출력되어 출력 HDD에 저장된다.
  • 입력과 출력 HDD의 역할을 바꾼다 = 출력 HDD가 입력 HDD, 입력 HDD는 출력 HDD로 사용된다.

 

 

➰ 128GB입력과 1GB의 주기억 장치에 대한 ExternalSort의 수행과정을 블록의 크기와 개수로 살펴보자.

• 1GB의 정렬된 블록 128개가 별도의 HDD에 저장된다.
• 2GB의 정렬된 블록 64개가 출력 HDD에 저장된다.
• 4GB의 정렬된 블록 32개가 출력 HDD에 저장된다.
• ...
• 128GB의 정렬된 블록 1개가 출력 HDD에 만들어지고, while-루프의 조건이 '거짓'이 되어, 출력 HDD를 반환한다.

 

 

3️⃣ 외부정렬의 시간 복잡도

• 전체 데이터를 몇번 처리 (읽고 쓰기) 하는가를 가지고 시간복잡도를 측정한다.
• 전체 데이터를 읽고 쓰는 것을 패스(pass)라고 한다.
• 따라서 while-루프가 수행된 횟수가 위 알고리즘의 시간복잡도가 된다.

• 입력의 크기가 N이고, 메모리 크기가 M이라고 하면, line 3이 수행될 때마다 블록 크기가 2M, 4M, 2^kM으로 (2배씩)증가한다. (k: 루프횟수).
  • 만약 만들어진 1개의 블록크기가 2^kM이라고 하면 이 블록은 입력 전체가 합병된 결과를 가지고 있으므로, 2^kM = N
  • 여기서 k는 while-루프가 수행된 횟수!
  • 따라서, 2^k = N/M, k=log(N/M)

따라서 외부 정렬의 시간복잡도는 O(log(N/M)) !

 

---

External 알고리즘에서는 하나의 보조 기억 장치에서 2개의 블록을 동시에 주기억 장치로 읽어 들일 수 있다는 가정하였다.

그러나, 2개의 블록이 각각 다른 보조 기억 장치에서 읽어들여야하는 경우가 있다.

예를들어, 테이프 드라이브 같은 저장장치는 블록을 순차적으로만 읽고 쓰는 장치이므로, 2개의 블록을 동시에 주기억 장치로 읽어 들일 수 없다.

테이프 드라이브 (Tape Drive)

• 그림에서 블록 1이 [10 30 60 70], 블록 2가 [20 40 50 80]인데, 이 2개의 블록을 합병하려면, 블록 1의 10을 읽고 블록 2의 20을 읽어서 비교해야한다.
• 그러나, 한쪽 방향으로만 테이프가 감기므로 되감아야하는 문제가 발생!
• 테이프 드라이브와 같은 보조기억 장치를 사용하는 경우에는 ExternalSort 알고리즘의 2개의 블록을 읽어들여 합병하면서 만들어지는 블록을 2개의 저장 장치에 번갈아 가며 저장하면 된다.

예제 ) 다음은 8개의 정렬도니 블록이 테이프 드라이브(TD) 0과 1에 각각 4개씩 저장되어 있는 상태에서, 2개의 보조 테이프 드라이브를 추가로 사용하여, 1개의 블록으로 합병시키는 과정을 보이고 있다.

 

• ExternalSort 알고리즘은 2개의 블록을 쌍으로 합병하므로 2-way 합병(merge)이라고 한다.
• 2-way 합병보다 빠르게 합병하는 다방향 합병 알고리즘이 있는데, 이 경우의 시간 복잡도는 O(log(p)(N/M))이다.
• 그러나 다방향 합병 알고리즘은 2p개의 보조 기억 장치를 필요로 한다.
• 이러한 단점을 보완하기 위해 (p+1)개의 보조 기억 장치만을 가지고 p-way 합병을 하는 다단계 합병 알고리즘이 있다.
  
  

4️⃣ 응용

• 물품/재고 DB,
• 인사DB등의갱신을위해사용
• 통신/전화 회사의 전화 번호 정렬,
• 인터넷의 IP주소 관리,
• 은행에서의 계좌 관리
• 일반적인 DB의 중복된 데이터를 제거 등

 

---

Reference 

• 서울과학기술대학교 컴퓨터공학과 알고리즘 수업
• 알기쉬운 알고리즘 도서