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



맨위로
통합 검색어 입력폼