7.1 정렬의 개요
• 자료가 저장되는 위치 : 내부 정렬(internal sort), 외부 정렬(external sort)
• 내부 정렬 : 정렬되는 자료의 개수가 적어서 자료를 주기억 장치에 모두 적재(load)시켜 놓고 정렬하는 방법
• 외부 정렬 : 자료의 개수가 너무 많아 주기억 장치의 크기가 부족하여 자료를 보조 기억 장치에 저장한 후 자료의 일부분만 차례로 주기억 장치로 적재하여 정렬하는 방법
• 내부 정렬 종류
① 삽입법 : 삽입 정렬(Insertion sort), 쉘 정렬(Shell sort)
② 교환법 : 선택 정렬(Selection sort), 버블 정렬(Bubble sort), 퀵 정렬(Quick sort)
③ 선택법 : 히프 정렬(Heap sort)
④ 분배법 : 기수 정렬(Radix sort)
⑤ 병합법 : 2-원 병합 정렬(2-way merge sort), 병합 정렬(merge sort)
• 외부 정렬 종류
① 디스크를 이용한 정렬 : 2-원 병합 정렬(2-way merge sort), m-원 병합 정렬(m-way merge sort)
② 테이프를 이용한 정렬 : 균형 병합 정렬(Balanced merge sort), 다단계 병합 정렬(Polyphase merge sort), 계단식 병합 정렬(Cascade merge sort), 교대식 병합 정렬(Oscillating merge sort)
• 정렬은 주어진 환경에 따라 최적의 알고리즘을 선택해야 함
• 정렬 알고리즘을 선택할 때 고려해야 할 사항 : 사용되는 컴퓨터 시스템의 특성, 정렬할 자료의 양 , 초기 자료의 배열 상태, 키 값의 분포 상태, 작업 공간의 크기, 자료의 이동 회수, 키의 비교 회수
7.2 내부 정렬(Internal Sort)
• 속도가 외부 정렬에 비해 빠름
• 정렬은 일반적으로 키 값에 대해 오름차순으로 이루어짐
7.2.1 버블 정렬(Bubble Sort)
• 버블 정렬 : 정렬의 기본이 되는 알고리즘
ⓐ 주어진 자료에서 제일 첫 레코드에서 시작하여 두 개의 인접한 레코드 키를 비교하여 키 값의 크기에 따라 레코드의 위치를 교환한다.
ⓑ 이 과정에서 첫 번째와 두 번째 레코드를 비교하여 크기 순으로 재배치하고, 두 번째와 세 번째 레코드를 비교하여 크기순으로 재배치한다.
ⓒ 이런 과정은 마지막으로 n-1번째와 n번째 레코드를 비교하여 크기순으로 재배치하면 1회전(1-pass)의 단계가 끝난다.
ⓓ 1회전이 끝나면 제일 큰 레코드가 자료의 마지막에 위치한다.
ⓔ 만약, 2회전이 끝난다면 두 번째로 큰 레코드가 n-1번째에 위치한다.
ⓕ 이러한 과정은 n-1 회전이 되면 정렬이 완료된다.
• 1회전이 끝나면 제일 큰 레코드가 제일 끝에 위치하므로
→ 2회전을 수행할 때는 제일 마지막에 위치한 n번째 레코드와 n-1번째 레코드는 비교할 필요가 없다.
• 또한 2회전이 끝나면 두 번째로 큰 레코드가 n-1번째에 위치하므로
→ 3회전을 수행할 때는 n-1번째 이후의 레코드와 n-2번째 레코드는 비교할 필요가 없다.
• 즉 회전이 거듭될수록 비교하는 회수가 1씩 감소한다.
2회전 때는 비교 회수가 1회, 3회전 때는 비교 회수가 2회, n-1회전 때는 비교 회수가 (n-1)-1회 감소 , 이렇게 알고리즘을 작성하면 수행 속도가 빨라진다.
• 단점 : 이미 정렬이 끝난 상태에서도 n-1회전까지 수행된다는 점
즉 알고리즘이 수행되는 중간에 이미 정렬이 완료된 상태이더라도 알고리즘은 n-1회전까지 수행
→ 해결 : 플래그(flag)를 두어 어떤 회전이 끝날 때까지 자료의 교환이 없으면 알고리즘의 수행을 끝내게 하면 됨
• 버블 정렬 알고리즘
<플래그를 사용하지 않을 경우>
void bubble_sort_nonflag(int Array, n)
{
int i, j, n, temp;
for(i = 0; i < n-1; i++)
{
for(j = 0; j < (n-1)-i; j++)
if(Array[j] > Array[j + 1]
{
temp = Array[j];
Array[j] = Array[j + 1];
Array[j + 1] = temp;
}
}
}
[예제 7.1] n = 5인 경우 입력 레코드 9, 11, 4, 7, 8을 플래그가 없는 경우에 버블 정렬하시오.
< 플래그를 사용할 경우 >
void bubble_sort_flag(int *Array, n)
{
int i, j, flag, n, temp;
flag = 1 ;
while(flag > 0 && I <= n-1)
{
flag = 0;
for(j = 0; j < (n - 1) - i; j++)
if(Array[j] > Array[j + 1]
{
temp = Array[j]
Array[j] = Array[j + 1];
Array[j + 1] = temp;
flag = 1;
}
}
}
[예제 7.2] 예제 4.1이 플래그가 있을 때 버블 정렬하시오.
• 레코드 교환 회수 : 입력 파일의 구조에 따라 달라지며 레코드의 비교 회수보다 크지 않다
• k번째 단계에서의 비교 회수는 (n - k)이고
최대 (n - 1)번의 회전이 수행
• 전체 정렬시간은 키의 비교 회수로 나타냄
키의 총 비교 회수 = (n - 1) + (n - 2) …+ 2 + 1
= 
• 그러므로 전체 수행 시간은 0(n2)
7.2.2 삽입 정렬(Insertion Sort)
• 이미 정렬된 n개의 레코드로 구성된 파일에 새로운 레코드를 적절한 위치에 삽입하는 과정을 반복하는 정렬
• 삽입된 레코드가 포함된 파일은 계속 정렬 상태를 유지
• 삽입 정렬은 다음과 같이 진행
ⓐ 두 번째 키를 기준으로 첫 번째 키와 두 번째 키를 비교하여 키 값의 크기에 따라 순서대로 두 개의 레코드를 나열하고,
ⓑ 다시 세 번째 키를 기준으로 첫 번째 키와 두 번째 키를 비교하여 키 값의 크기에 따라 순서대로 3개의 레코드를 나열한다.
ⓒ 계속해서 n번째 키를 앞의 n-1개의 키와 비교하여 삽입 될 적당한 위치를 찾아 삽입한다.
ⓓ 삽입 후에는 삽입된 이후에 위치한 레코드들은 한 레코드는 한 레코드씩 뒤로 이동한다.
• 삽입 정렬의 알고리즘
void insertion_sort(int Array, n)
{
int i, j, n, temp;
for(i = 1; i < n-1; i++)
{
temp = Array[i];
j = i - 1;
while(j > = 0 && (temp < Array[j] ))
{
Array[j + 1] = Array[j];
--j;
}
Array[j + 1] = temp;
}
}
[예제 7.3] n이 5인 경우 입력 레코드 9, 11, 4, 7, 8을 삽입 정렬하시오.
• i번째 레코드를 삽입할 위치를 찾는데 : 평균적으로 i/2번 소요
→ 수행 시간은 0(i)
• (n - 1)개의 레코드를 삽입하는데 소요되는 시간 : 최악의 경우 레코드 전체가 역으로 정렬되어 있는 경우
• 전체 수행 시간은 O(n2)
•최소의 경우 : 레코드가 정렬하고자 하는 순서대로 정렬되어 있는 경우 → (n - 1)번이며 0(n)이다
7.2.3 선택 정렬(Selection Sort)
• 특정 레코드를 선택하여 지정된 위치에 있는 레코드와 교환하는 방식
• 선택 정렬은 다음과 같이 진행
ⓐ 레코드에서 가장 작은 키 값을 가지는 레코드를 찾아 첫번째 레코드와 교환하고,
ⓑ 교환 후 첫번째 레코드를 제외한 (n -1)개의 레코드 중에서 가장 작은 키 값을 갖는 레코드를 찾아 두 번째 위치에 있는 레코드와 교환한다.
ⓒ 이후의 레코드들에 대해서도 이 과정을 반복적으로 수행한다.
ⓓ 주의할 점은 삽입하는 것이 아니고 교환하는 것이다.
• 선택 정렬 알고리즘
void selection_sort(int Array, n)
{
int i, j, n, k temp;
for(i = 0; i < n-1; i++)
{
temp = Array[i];
k = i;
for(j = i + 1; j < n - 1; j++)
{
if(temp > Array[j])
{
temp = Array[j];
k = j;
}
}
temp = Array[k];
Array[k] = Array[i];
Array[i] = temp;
}
}
[예제 7.4] n이 5인 경우 입력 레코드 9, 11, 4, 7, 8을 선택 정렬하시오.
• 최소 값을 찾기 위해 (n -1)번 키 값을 비교하게 되며, 총 비교 회수는
• 전체 수행 시간은 O(n2)이다
7.2.4 쉘 정렬(Shell Sort)
• 특정 레코드와 거리가 일정한 레코드끼리 부파일로 나누어
→ 각 부파일을 삽입 정렬하는 방식
• 부파일로 나누기 위해 거리 h를 점점 작게하여
→ h가 1이 되면 정렬이 끝난다.
• 부파일로 나누는 방법은 만약 h가 5라면
첫 번째 부파일 : 첫 번째 레코드
6번째 레코드
11번째 레코드
두 번째 부파일 : 2, 7, 12 … 레코드
• 나누어진 부파일은 삽입 정렬을 이용하여 정렬
• h는 증분(increment)이라 하며, 부파일의 수와 같다
• 쉘 정렬 알고리즘
void shell_sort(int Array, n)
{
int i, j, k, n, h, temp;
h = n/2;
while(h > 0)
{
for(i = 0; i < h; i++)
{
for(j = i + h; j < n; j = j + h)
{
for(k = j - h; k > = i; k = k - h)
{
if(Array[k] > Array[k + h]) then
{
temp = Array[k];
Array[k] = Array[k+h]
Array[k+h] = temp;
}
else
break;
}
}
}
h = h/2;
}
}
[예제 7.5] n = 12인 경우 입력 레코드 10, 28, 86, 65, 35, 25, 42, 17, 54, 45를 h = 5, 3, 2, 1을 적용시켜 쉘 정렬하시오
① h = 5일 때
② h = 3일 때
③ h = 2일 때
④ h = 1일 때
• h는 근사적으로 1.72 
으로 소수(prime number)
• 적당한 증분값에 대하여 수행 시간은 O(n(logn)2)
7.2.5 기수 정렬(Radix Sort)
• 기본적으로 수치 자료를 정렬하기 위해 만들어졌음
• 각 자료가 여러 개의 키를 가지고 있어 이 키들을 순차적으로 적용시켜 자료를 정렬
• 기수 정렬은 다음과 같이 진행
ⓐ 수치 자료에 여러 개의 키 중 첫 번째 키를 적용시킨 후 정렬된 자료를 해당 버킷(bucket)에 분배한다.
ⓑ 버킷에 있는 분배된 자료를 차례대로 꺼내와 두 번째 키를 적용시켜 정렬된 자료를 해당 버킷에 분배한다.
ⓒ 이 과정을 키의 개수만큼 반복하여 정렬을 완료한다.
• 수치 자료의 키 : 단 단위, 백 단위, 십 단위, … 각각 10개의 버킷이 필요
• 기수 정렬의 알고리즘
struct bucked;
{
int key;
struct bucket *next;
}
* BUCKET[digit]
void radix_sort(int array, n, s)
{
int *array, n, s ;
int i, j, num;
for(i = 1; i < = s; i++)
{
switch(i)
{
case 1 : for(j = 1; j <= n ; j++)
{
num = array[j] %10;
INSERT_BUCKET(array[j], BUCKET[num] );
}
break;
case 2 : for(j = 1; j <= n; j++)
{
num = (array[j]/10)%10;
INSERT_BUCKET(array[j], BUCKET[num] );
}
break;
case 3 : for(j = 1; j <= n; j++)
{
num = (array[j]/10)%10;
INSERT_BUCKET(array[j], BUCKET[num] );
}
}
}
}
[예제 7.6] n = 12인 경우 입력 레코드 10, 28, 86, 65, 35, 25, 42, 17, 54, 45를 기수 정렬하시오.
① 단 단위 숫자에 대해 정렬
② 십 단위 숫자에 대한 정렬
• 키의 개수가 n일 때 비교 회수는 각각의 레코드에 대해 n번씩 수행
• 또한 레코드의 개수가 m개이고 기수가 b일 때 매 수행마다 O(m + b)의 수행 시간이 요구
• 전체 수행 시간은 O(n(m + b))
7.2.6 병합 정렬(Merge Sort)
• 이미 정렬된 두 개의 파일을 정렬하여 한 개의 다른 파일로 만드는 것
• 병합 정렬은 다음과 같이 진행
ⓐ 각 파일에서 차례로 한 레코드씩 가져와 비교하여 키 값이 작은 레코드를 새로 만들어진 파일에 저장한다.
ⓑ 작은 키를 가졌던 파일에서 다음 순서의 레코드를 다시 가져와서 이미 가져와 이전에 비교된 큰 키 값을 가진 레코드와 비교하여 키 값이 작은 레코드를 새로 만들어진 파일에 저장한다.
ⓒ 이 과정을 반복적으로 수행하면 정렬된 새로운 한 개의 파일이 만들어진다.
• 병합 정렬 알고리즘
void merge_sort(file_a, file_b)
{
int file_c;
int a_ptr, b_ptr, c_ptr;
a_ptr = b_ptr = c_ptr = 0;
while(a_ptr < M && b_ptr < N) /* M : file_a 에 저장된 자료의 개수
N : file_b 에 저장된 자료의 개수 */
{
if(file_a[a_ptr] <= file_b[b_ptr]);
then
file_c[c_ptr++] = file_a[a_ptr++];
else
file_c[c_ptr++] = file_b[b_ptr++];
}
while(a_ptr < M)
file_c[c_ptr++] = file_a[a_ptr++]; /* file_a의 나머지 자료를 file_c 에 넣는다. */
while(n_ptr < N)
file_c[c_ptr++] = file_b[b_ptr++]; /* file_b의 나머지 자료를 file_c 에 넣는다. */
}
[예제 7.7] file1 = (1, 3, 5)이고, file2 = (2, 4, 6, 8, 9)일 때 file3으로 병합 정렬하여 보자.
초기 파일 file1 = (1, 3, 5), file2 = (2, 4, 6, 8, 9)
1회 file3 = (1)
2회 file3 = (1, 2)
3회 file3 = (1, 2, 3)
4회 file3 = (1, 2, 3, 4)
5회 file3 = (1, 2, 3, 4, 5)
6회 file3 = (1, 2, 3, 4, 5, 6, 8, 9) --- file1이 비었으므로 file2의 나머지 자료를 file3에 모두 넣는다.
• 첫 번째 while문이 합병 연산의 중심 부분으로, 각 배열에서 하나씩 꺼내와 비교 후 작은 것을 새로운 배열에 넣는 연산
마지막에 있는 두 개의 while문은 두 배열 중 어느 한쪽이 끝나면 다른 한 쪽에 있는 자료를 새로운 배열에 비교 없이 넣는 연산
→ 그러므로 3개의 while문을 수행하는데 걸리는 시간은 O(m + n)
7.2.7 2-원 병합 정렬(2-way Merge Sort)
• 분할 정복(divide-conquer) 기법을 기초로 하여 정렬
• 2-원 병합 정렬은 다음과 같이 진행
ⓐ 주어진 레코드들을 각각 크기가 1인 정렬된 파일로 간주하여 두 파일을 병합 정렬하고,
ⓑ 그 다음 크기가 2인 파일들을 간주하여 두 파일을 병합 정렬한다.
ⓒ 이 과정을 반복 수행하면 2-원 병합 정렬이 수행된다.
void merge(int filea, int n)
{
int size;
int fileb[ ];
size = 1;
while(size < n)
{
MPASS(filea, fileb, n, size);
size *=2;
MPASS(fileb, filea, n, size);
size *=2;
}
}
void MPASS(int *filea, int *fileb, int n, int size)
{
int i, t;
i = 1;
while(i <= (n -2 * size + 1))
{
MERGE(filea, fileb, i, i + size-1, i + 2 *size-1);
i = i + 2 *size;
}
if(i + size-1 < n) then
MERGE(filea, fileb, i + size-1, n);
else
for(t = i; t <=n; t++) fileb[t] = filea[t];
}
• i번째 단계에서는 병합될 파일의 크기가 2i-1개
→ 따라서 n개의 레코드에 대해서 log n번의 단계가 수행
• 두 개의 파일을 병합하는데 O(n)이 소요
• 총 소요 시간은 O(nlog n)이다.
[예제 7.8] n = 10이고 입력 레코드가 4, 2, 7, 8, 5, 9, 3, 6, 1, 10일 때
2원 병합 정렬하시오.
7.2.8 퀵 정렬(Quick Sort)
• 지금까지 배운 알고리즘보다 평균 수행 능력이 더 좋음
• C.A.R Hoare에 의해 개발
• 특정한 키 값보다 큰 값을 갖는 레코드들과 작은 값을 갖는 레코드들로 분리되어 → 한 개의 파일이 두 개의 부파일로 재배열
• 또한 이 분리된 각각의 부파일에 퀵 정렬 알고리즘을 적용하며
→ 이 과정을 반복하면 파일이 정렬된다
• 퀵 정렬 다음과 같이 진행
ⓐ 퀵 정렬은 처음 레코드 R1을 제어 키(control key) 또는 피봇 키(pivot key)로 두고
ⓑ 왼쪽에서 오른쪽으로 진행하면서 R1보다 큰 키 값을 찾고, 오른쪽에서 왼쪽으로 진행하면서 R1보다 작은 키 값을 찾아 서로 교환한다.
ⓒ 그런 후 이 과정을 반복하다가 왼쪽 키 값과 오른쪽 키 값이 서로 교차하면 중지하고, R1을 제일 마지막에 찾은 R1보다 작은 키 값과 교환한다.
ⓓ 교환 후 교환된 R1을 기준으로 왼쪽 부파일과 오른쪽 부파일로 분할하여, 각각의 부파일을 다시 퀵 정렬한다.
ⓔ 만약 제어 키 보다 큰 키 밖에 없으면 제어 키 다음 키를 제어 키로 정하고 다시 오른쪽 나머지 레코드를 퀵 정렬한다.
ⓕ 만약 제어 키보다 작은 키만 존재하면 제어 키와 처음 찾은 제어 키보다 작은 키 값을 교환하고 분할하여 다시 퀵 정렬한다.
• 퀵 정렬 알고리즘
void quick_sort(int file, m, n)
{
int left_ptr, right_ptr, key, temp;
if(m < n)
{
left_ptr = m;
right_ptr = n + 1;
key = file[m];
do
{
++ left_ptr;
--right_ptr;
while(file[left_ptr] < key) left_ptr++;
while(file[right_ptr] > key) right_ptr--;
if(left_ptr < right_ptr)
{
temp = file[left_ptr];
file[left_ptr] = file[right_ptr];
file[right_ptr] = temp;
}
while(left_ptr < right_ptr)
{
temp = file[left_ptr];
file[left_ptr] = file[right_ptr];
file[right_ptr] = temp;
}
quick_sort(file, m, right_ptr-1);
quick_sort(file, right_ptr+1, n);
}
}
}
[예제 7.9] n = 9일 때 다음 입력 레코드 35, 25, 45, 50, 30, 15, 37, 48, 21을 퀵 정렬하시오.
• 한 레코드의 위치를 결정하기 위해 n번 비교
→ 그 후 부파일에 대해 n/2번 비교, 그리고 부파일에 대해 n/2번 비교, 계속 수행하면 n/4, n/8, …, n/2k번 비교, 비교 회수가 log2n번으로 줄어든다
• 수행 시간은 O(nlogn)
7.2.9 히프 정렬(Heap Sort)
• 히프(heap)라는 자료 구조를 사용하여 정렬하는 알고리즘
• 히프 : 전이진 트리로서 각 노드의 키 값이 자식 노드의 키 값보다 작지않은 트리이다.
• 히프 : 전이진 트리이므로 노드의 삽입과 삭제가 발생해도 히프의 성질은 만족해야 한다 → 즉, 히프로 재구성해야 한다
• 히프의 특성 상 근노드에 제일 큰 값이 있으므로 근노드를 제거한 후 트리를 재구성한다 → 이 과정을 반복적으로 수행하면 레코드들은 정렬됨
• 히프 정렬은 다음과 같이 두 가지 단계로 구성
ⓐ 주어진 입력 트리를 히프로 바꾼다.
ⓑ 히프의 근노드와 제일 마지막 노드를 교환하고, 이 트리를 히프가 되도록 한다. 단, 교환된 마지막 노드는 마지막 노드로 간주하지 않는다.
ⓒ 위의 ⓑ과정을 정렬이 끝날 때까지 반복한다.
• 히프 정렬 알고리즘
void heap_sort(int *array, int n)
{
int i, temp;
for(i = n/2; i >= 1; i--) reheap(array, i, n);
for(i = n-1; i >= 1; i--)
{
temp = array[i+1];
array [i + 1] = array[1];
array[1] = temp;
reheap(array,1, i);
}
}
void reheap(int *array, int i, int n)
{
int j, k, m;
boolean flag;
flag = FALSE;
m = k = array[i];
j = 2 *i;
while(j <= n && !flag)
{
if(j < n)
if(array[j] < array[j + 1] ) j = j + 1;
if(k >= array[j]) flag = TRUE;
else
{
array[j/2] = array[j];
j = j * 2;
}
}
array[j/2] = m;
}
[예제 7.10] 다음 트리를 히프로 변환하여 히프 정렬하시오.
7.3 외부 정렬(External Sort)
• 정렬하려는 파일의 크기가 너무 커서 주기억 장치에 적재할 수 없어
→ 보조기억 장치인 디스크나 테이프를 이용하여 정렬을 수행
• 외부 정렬의 단계 :
→ 우선 주기억 장치에 적재 가능한 크기로 여러 개의 부파일로 나눈다
→ 그 다음 나누어진 각 부파일을 내부 정렬 알고리즘으로 정렬한 후 다시 보조 기억 장치에 저장하고
→ 정렬된 여러 개의 부파일을 다시 하나의 파일로 병합 정렬하여 정렬을 완료
7.3.1 디스크를 이용한 정렬
• 보조 기억 장치인 디스크는 직접 접근(direct access)이 가능한 장치로 각 부파일을 병합하여 읽거나 쓰는 위치는 크게 중요하지 않다
• 또한 입출력 버퍼(buffer)로 사용할 수 있는 주기억 장치의 여유만 있으면 여러 개의 부파일을 동시에 병합
7.3.1.1 2-원 병합 정렬(2-way Merge Sort)
• 외부 정렬을 수행할 때 가장 많이 사용되는 정렬 방식
• 정렬은 다음과 같이 진행
ⓐ 입력 파일의 일부를 주기억 장치에 적재한 후 내부 정렬을 수행한다.
ⓑ 이렇게 정렬된 부파일을 런(run)이라 하며 외부 기억 장치에 하나의 파 일로 저장한다.
ⓒ 이렇게 만들어진 여러 개의 런을 병합 정렬을 이용하여 런을 2개씩 병합하여 하나의 런이 될 때까지 수행한다.
[예제 7.11] “ASORTINGANDMERGING"을 이용하여 디스크를 이용한 2원 병합 정렬을 하시오.(단, 런은 6개이다.)
7.3.1.2 m-원 병합 정렬(m-way Merge Sort)
• 각 런에서 자료를 하나씩 꺼내와 선택 트리(selection tree)를 만듬
• 정렬은 다음과 같이 진행
ⓐ 각 런에서 자료를 하나씩 꺼내와 선택 트리(selection tree)를 만든다. 이 트리는 모든 노드의 키 값이 자식 노드의 키 값보다 작다.
ⓑ 이 선택 트리에서 근노드를 제거한 후 다시 선택 트리를 만든다.
ⓒ 이 과정을 반복하면 정렬이 완성된다.
[예제 7.12] 9, 15, 18, 10, 14, 17, 11, 13, 16, 12, 14, 19를 4개의 런을 이용하여 4-원 병합 정렬하시오.
결과 : 9, 10, 11, 12, 13, 14, 14, 15, 16, 17, 18, 19
7.3.2 테이프를 이용한 정렬
• 테이프를 이용한 정렬의 경우 인접한 블록들이 저장된 위치에 따라 입출력 시간이 크게 차이가 난다
→ 그러므로 병합 정렬에 입력될 블록들은 반드시 연속적으로 저장되어 있어야 한다.
7.3.2.1 균형 병합 정렬(Balanced Merge Sort)
• k개의 테이프를 이용한다면 각 테이프에 같은 개수의 레코드(자료)들을 분배하여 내부 정렬을 이용하여 병합하는 방법
• 균형이라는 말은 입력된 런의 수와 출력된 런의 수가 같다는 것
• 균형 병합 정렬이 이루어지는 순서
ⓐ 초기 파일을 (준비된 테이프의 개수) /2개의 부파일로 나눈다.
ⓑ 각 부파일을 내부 정렬하여 런(레코드 1개)을 만들어 (준비된 테이프의 개수) /2개의 테이프에 균등하게 교대로 보관한다.
ⓒ 각 테이프에 수록된 런들을 하나씩 읽어 병합 정렬하여 두 배로 된 런들을 다른 빈 테이프에 교대로 수록한다.
ⓓ 두 배로 된 런을 한 개의 런으로 간주하여, 전체 레코드가 한 개의 런으로 병합될 때까지 반복한다.
[예제 7.13] 런의 개수가 8개이고 테이프는 4개일 때 16, 17, 15, 20, 31, 18, 2, 8 을 균형 병합 정렬하시오.
7.3.2.2 계단식 병합 정렬(Cascade Merge Sort)
• 불균형한 병합 정렬로서 여러 개의 테이프로 작업을 진행한다
• 계단식 병합 정렬은 다음과 같이 진행
ⓐ 최초의 부파일을 한 개의 테이프는 비워둔 채로 k-1개의 테이프에 내부 정렬하여 분산 기록한다.
ⓑ 레코드가 수록된 테이프에서 레코드를 읽어 그 중 한 개의 테이프가 빌 때까지 (k-1)-원 병합 정렬하여 비어 있는 테이프에 기록한다.
ⓒ 다음에는 병합하지 않은 k-2개의 테이프 내용을 그 중 한 개의
테이프가 빌 때까지 (k-2)-원 병합 정렬한다.
ⓓ 같은 방식으로 병합하지 않은 테이프가 없을 때까지 반복한다.
[예제 7.14] 런의 개수가 12개이고, 테이프는 5개일 때 37, 25, 30, 19, 43, 8, 14, 6, 22, 3, 34, 26을 계단식 병합 정렬하시오.
7.3.2.3 다단계 병합 정렬(Polyphase Merge Sort)
• 출력 파일 수를 입력 파일 수만큼 사용하지 않고도 큰 병합 정렬 성능을 발휘하는 불균형 병합 정렬임
• 테이프의 개수가 6개 이하일 때 최적의 성능 발휘
• 계단식 병합 정렬은 다음과 같이 진행
ⓐ 부파일의 수를 피보나치 수열에 맞추어 n-1개의 테이프에 분배한다.
ⓑ 레코드가 수록된 테이프에서 런(레코드 1개)을 하나씩 읽어 그 중 한 개의 테이프가 빌 때까지 병합 정렬하여 비어 있는 테이프에 기록한다. 정렬된 레코드들이 하나의 런이 된다.
ⓒ 다시 다른 하나의 테이프가 빌 때까지 각 테이프에서 런을 하나씩 읽어 병합 정렬하여 다른 빈 테이프에 수록한다.
ⓓ 전체 레코드가 한 개의 런으로 병합될 때까지 반복한다.
[예제 7.15] 런의 개수가 9개이고, 테이프가 4일 때 19, 8, 14, 22, 34, 26, 14, 6, 43을 다단계 병합 정렬 해보자.
7.3.2.4 교대식 병합 정렬(Oscillating Merge Sort)
• 순방향(forward)과 역방향(reverse)이 가능한 테이프를 사용하여 정렬
• 정렬은 다음과 같이 진행
ⓐ 빈 테이프 1개를 제외한 나머지 테이프에 하나의 부파일을 분배한 후, 병합 정렬한 후 빈 테이프에 수록한다.
ⓑ 그 다음 결과가 수록된 테이프를 포함하고 빈 테이프 1개를 제외한 나머지 테이프에 하나의 부파일을 분배한 후, 병합 정렬하여 빈 테이프에 수록한다.
ⓒ 이 과정을 결과가 수록된 테이프를 하나씩 늘려가며 반복 수행하고, 마지막에는 모든 테이프를 병합 정렬하여 빈 테이프에 수록한다.
[예제 7.16] 런의 개수가 9개이고 테이프가 5개일 때 16, 2, 46, 10, 22, 31, 26, 27, 3, 23, 15, 29를 교대식 병합 정렬하시오(그림에서 ㆍ은 R/W 헤드의 위치이다).
출처 - http://www.dal.pe.kr/lecture/db_stru/ch07_sort.htm
