nlogn's log :: 천천히 달리기

//Quick Sort Functions for Descending Order
// (2 Functions)
void QuickSort(apvector <int> &num, int top, int bottom)
{
      // top = subscript of beginning of array
      // bottom = subscript of end of array
     
     int middle;
     if (top < bottom)
    {
          middle = partition(num, top, bottom);
          quicksort(num, top, middle);   // sort first section
          quicksort(num, middle+1, bottom);    // sort second section
     }
     return;
}

//Function to determine the partitions
// partitions the array and returns the middle subscript
int partition(apvector <int> &array, int top, int bottom)
{
     int x = array[top];
     int i = top - 1;
     int j = bottom + 1;
     int temp;
     do
     {
           do     
           {
                  j - -;
           }while (x >array[j]);

          do  
         {
                 i++;
          } while (x <array[i]);

          if (i < j)
         { 
                 temp = array[i];   
                 array[i] = array[j];
                 array[j] = temp;
         }
     }while (i < j);    
     return j;           // returns middle subscript 
}

※ stdlib.h 파일에는 qsort() 라는 훌륭한 함수가 존재한다. 해당 함수를 활용하여도 무방하다.

※ 함수 설명
두 함수 모두 비재귀 형식의 퀵소트이며
- quick_sort1() 함수는 : 세값의 중위 분할을 통한 퀵소트로, 삽입정렬을 사용한다.
- quick_sort2() 함수는 : 난수 분할을 통한 퀵소트이며, 삽입정렬을 사용한다.

이 첨부 파일에 있는 건 일반적인 함수의 형태이다. (int형 뿐 아니라 모든 형태의 자료형을 비교할 수 있도록 만든 것이다)
자료 배열의 선두 번지인 base,
자료의 개수 nelem,
레코드의 크기 width,
키값의 비교를 하는 함수 포인터 fcmp 를 뜻한다.
fcmp 함수는
int intcmp(const void *a, const void *b) 등을 뜻한다.

■ 퀵 정렬 개념

주어진 입력 리스트를 피봇(pivot) 또는 제어키(control key)이라 불리는 특정 키 값보다 작은 값을 가지는 레코드들의 리스트와 큰 값을 가지는 레코드들의 리스트로 분리한 다음, 이러한 두 개의 서브 리스트들을 재귀적으로 각각 재배열하는 과정을 수행하는 방식
퀵 정렬 방법은 하나의 커다란 입력 데이터의 집합을 정렬하는 것보다는 두개의 작은 입력 데이터들을 정렬하는 것이 빠르다는 일반적인 사실에 바탕을 둠
분할 및 정복 방법 사용
피봇(Pivot)이라 부르는 특정한 데이터를 기준으로 피봇보다 작은 값을 가진 데이터들은
배열의 왼쪽 부분에, 큰 값을 가진 데이터는 오른쪽에 위치하도록 배열
퀵 정렬은 기본적으로 순환(recursive) 알고리즘 형태를 취하며, 오름차순으로 정렬할 경우 레코드 R1을 제어 키 또는 피봇 키로 하여 왼쪽으로 가면서 R1보다 큰 키 값을 찾고, 오른쪽으로부터 왼쪽으로 가면서 R1보다 작은 키 값을 찾아 서로 교환한다. 위의 과정이 수행될 때 오른쪽과 왼쪽이 서로 교차하면 중지하고 R1을 제일 나중에 찾은 R1보다 작은 키 값과 교환하면 R1보다 작은 키 값을 갖는 레코드들과 큰 키 값을 갖는 레코드들로 분할되어 하나의 파일이 제어키 R1을 기준으로 두 개의 서브 파일로 재배열된다. 재배열된 서브파일에 대해 독립적으로 위의 수행 과정을 반복하면 정렬이 완료된다.

■ 퀵 정렬 알고리즘 단계 : 분할과 정복 방식
① 피봇(Pivot) : 정렬할 데이터 S에서 하나 v를 선택한다.
② 분할 : S1 = {v보다 작은 수}, v, S2 = {v보다 큰 수}
③ 재귀적 수행 : return {퀵 정렬(S1), v, 퀵 정렬(S2)}

■ 특징
▷ 평균 연산 시간에 있어서 내부 정렬 방법 중 가장 우수
     - 실제 수행속도가 가장 빠른 정렬 알고리즘
▷ 스택 공간을 사용
▷ 재귀 호출을 기반으로 동작

■ 퀵 정렬 알고리즘

-----------------------------------------------------------------------------
void Quicksort(int A[], int N) {Qsort(A,0, N-1); }      /* 퀵 정렬 호출 함수 */

int Median3(int A[], int Left, int Right)                       /* 세 수의 중위수 계산 함수 */
{      int Center= (Left + Right) / 2;              /* A[Left]<= A[Center]<= A[Right]*/
        lf( A[Left] > A[Center] ) Swap( &A[Left], &A[Center] );
        if( A[Left] > A[Right] )  Swap( &A[Left], &A[Right] );
        if( A[Center] > A[Right]) Swap(&A[Center], &A[Right]);
        swap( &A[Center], &A[Right-1] );   /* 피봇된 수를 오른쪽-1의 위치에 있는 수와 SWAP */
        return A[Right-1];                            /*return 피봇 */
}

#define Cutoff(3)                                                     /* 퀵 정렬 함수 */
void Qsort( int A[], int Left, int Right )       /* 배열 A의 왼쪽 끝 첨자:Left, 오른쪽 끝 첨자:Right */
         {     int i, j, Pivot;                              
/*1*/       if( Left + Cutoff <= Right )          
/*2*/       {     Pivot = Median3( A, Left, Right);  
/*3*/              i=Left; j=Right-1;
/*4*/              for( ; ; )
/*5*/             {    while( A[++i ] < Pivot ){}
/*6*/                   while( A[--j ] > Pivot ){}
/*7*/                   if( i < j )
/*8*/                        swap( &A[ i ], &A[ j ] );
/*9*/                   else   break;
                      }
/*10*/            swap( &A[ i ], &A[ Right-1] );
/*11*/            Qsort( A, Left, i-1 );
/*12*/            Qsort( A, i+1, Right );  
                }
                else                            
/*13*/           InsertionSort( A+Left , Right-Left+1)        
           }

②세 수의 중위수 계산, Pivot에 중앙값 넣기
⑤배열의 왼쪽에서부터 중앙값보다 큰 원소까지
   이동
⑥배열의 오른쪽에서부터 원소의 값이 중앙값보다
   작은 원소까지 이동
⑦⑧⑨정렬이 끝나지 않았으면 중앙값보다 작은
   원소는 왼쪽에, 큰 원소는 오른쪽에 들어가도록
   교체함. 정렬이 끝났으면 무한루프를 벗어남
⑩중앙값보다 큰 첫 번째 요소와 중앙값을 교환해
   중앙값을 작은 값과 큰 값 사이에 끼워 넣음.
   중위치 정렬
⑪왼쪽부분리스트(중앙값보다 작은부분)의 퀵정렬
⑫오른쪽부분리스트(중앙값보다 큰부분)의 퀵정렬
⑬원소가 Cutoff보다 작거나 같은 서브트리의
   삽입정렬
-----------------------------------------------------------------------------

■ 성능

▷ 최악의 경우: O(n2)
▷ 평균: O(nlogn)
▷ 최선의 경우는 n 개의 데이터가 저장된 배열이 각 분할 단계에서 정확히 이등분 될 때
▷ 교환 및 비교 회수가 매우 적음 : 단순하고 매우 빠른 속도로 수행
▷ 안정성은 없음
▷ 난수 배열 및 반쯤 정렬된 배열 자료에 대해서는 성능이 우수
▷ 피봇이 중간 값을 갖도록 해야 수행속도가 좋아짐

//Function to merge two pre-sorted arrays
void MergeSort(apvector <int> &arrayA, apvector <int> &arrayB, apvector <int> &arrayC)
{
     int indexA = 0;     // initialize variables for the subscripts
     int indexB = 0;
     int indexC = 0;

     while((indexA < arrayA.length( )) && (indexB < arrayB.length( ))
     {
          if (arrayA[indexA] < arrayB[indexB])
          {
                 arrayC[indexC] = arrayA[indexA];
                 indexA++;    //increase the subscript
          }
         else
         {
                 arrayC[indexC] = arrayB[indexB];
                 indexB++;      //increase the subscript
         }
        indexC++;      //move to the next position in the new array
     }
     // Move remaining elements to end of new array when one merging array is empty
     while (indexA < arrayA.length( ))
     {
           arrayC[indexC] = arrayA[indexA];
           indexA++;
           indexC++;
     }
     while (indexB < arrayB.length( ))
     {
           arrayC[indexC] = arrayB[indexB];
           indexB++;
           indexC++;
     }
     return;
}

이 첨부 파일에 있는 건 일반적인 함수의 형태이다. (int형 뿐 아니라 모든 형태의 자료형을 비교할 수 있도록 만든 것이다)
자료 배열의 선두 번지인 base,
자료의 개수 nelem,
레코드의 크기 width,
키값의 비교를 하는 함수 포인터 fcmp 를 뜻한다.
fcmp 함수는
int intcmp(const void *a, const void *b) 등을 뜻한다.

■ 병합 정렬 개념

이미 순서적으로 배열된 두 개의 파일에서 레코드의 배열 순서에 따라 차례로 한 레코드씩 가져다 비교하여 작은 키 값을 가지는 레코드를 새로운 병합 파일에 출력하고, 작은 레코드를 가져온 파일에서 다음 순서의 레코드를 가져와 이전에 비교한 큰 키 값을 가진 레코드와 비교하는 과정을 반복 수행하므로 완전히 순서적으로 배열된 한 개의 파일을 만드는 것을 의미
병합 정렬(merge sort:합병 정렬)은 퀵 정렬과 마찬가지로 분할 정복 방식의 알고리즘
퀵 정렬에서는 분할되는 두 부분배열의 크기가 다를 수도 있고 이것 때문에 최악의 성능이 O(n2)으로 되었는데 병합 정렬에서는 두 부분배열의 크기가 항상 같게 분할 됨.
병합 정렬의 수행시간은 최악의 경우에도 O(NlogN)
병합 정렬은 별도의 임시 기억장소(배열)가 필요
실제로는 수행시간이 많이 걸리며, 외부정렬에 주로 활용

■ 병합 정렬 방법

병합 정렬은 전형적인 분할 정복 방법의 예
분할 정복 방법은 순환적으로 문제를 푸는 방법으로서 주어진 문제를 여러 개의 소문제로 분할하여 이 소문제를 순환적으로 푼 후 이들의 해를 결합하여 원래 문제의 해를 구하는 방식
즉, 순환 호출시 마다 다음과 같은 세 단계의 작업이 이루어짐
▷ 분할 : 주어진 문제를 여러 개의 소문제로 분할한다.

▷ 정복 : 소문제들을 순환적으로 처리하여 정복한다.
              만약 소문제의 크기가 충분히 작다면 순환 호출없이 소문제에 대한 해가 구해진다.

▷ 합병 : 소문제에 대한 해를 합병하여 원래 문제의 해를 구한다.

병합 정렬 알고리즘을 분할 정복 방법의 세 단계로 대응 시켜 보면 다음과 같음
① 분할 : 정렬할 n원소의 배열을 n/2 원소의 두 부분배열로 분할한다.

② 정복 : 두 부분배열에 병합 정렬을 각각 순환적으로 적용하여 두 부분배열을 정렬한다.

③ 합병 : 두 정렬된 부분배열을 머지하여 원래의 정렬된 배열을 만든다.

■ 머지 방법

두 정렬된 부분배열의 원소를 비교, 결합하여 하나의 정렬된 배열을 만든다.
두 부분 배열은 서로 인접하여 있으며 머지된 결과는 제자리에 남는다.
두 부분배열은 서로 인접하여 있기 때문에 이들의 위치를 표현하는데는 그들이 속해있는 배열명과 첫째 부분배열의 시작점과 끝점 그리고 두 번째 부분배열의 끝점을 나타내는 배열 첨자만 필요 (예) A[1:3]과 A[4:6]을 머지하려면 배열의 이름인 A와 첨자인 1,3,6만을 함수 Merge에 전달하면 됨
두 개의 부분배열을 머지하는 데는 그 두 부분배열을 합한 것만큼의 여분의 메모리 공간이 필요
- 배열 B가 그 여분 공간으로 사용됨

■ 병합 정렬 과정    

10개의 키가 있는 배열에 병합 정렬을 적용하는 과정을 보임
단계 1에 정렬하고자 하는 배열이 있음
단계 2~5에서는 MergeSort가 호출되어 각 단계마다 배열이 이분됨
단계 6~9에서는 함수 Merge가 호출되어 부분배열이 두 개씩 머지됨을 알 수 있음
각 경로에 붙어 있는 레이블은 병합 정렬 과정에서 취해지는 일의 순서를 나타냄
실제로 단계 1~5에 있는 레이블은 함수 MergeSort가 순환적으로 호출되는 순서이고,
단계 6~9의 레이블은 함수 Merge가 호출되어 행한 일을 나타냄

■ 병합 정렬 알고리즘
-------------------------------------------------------------------------------
   void MergeSort(int A[ ], int Low, int High) /* 입력: A[Low:High] - 정렬하려는 배열 */
   /* Low, High - 정렬할 원소가 있는 곳을 나타내는 최소, 최대 인덱스 */
   /* 출력: A[Low:High] - 정렬된 배열 */
       {              
              int Mid;    
/*a*/    if(Low < High)
              {
/*b*/           Mid = (Low + High)/2;
/*c*/           MergeSort(A[ ], Low, Mid);
/*d*/           MergeSort(A[ ], Mid+1, High);
/*e*/           Merge(A[ ], Low, Mid, High);
               }
       }  

ⓐif문은 '배열 원소가 둘 이상이면'의 의미를 나타냄 ⓑ둘 이상이면 그 배열의 중간위치를 구하고
ⓒ분할된 왼쪽의 부분배열에 대하여 MergeSort를 순환 호출하여 정렬하고, 왼쪽 부분배열의 정렬이 끝났으면
ⓓ오른쪽 부분배열에 대하여 MergeSort를 순환
호출하여 오른쪽 부분배열을 정렬함
ⓔ왼쪽과 오른쪽이 끝났으면 이들을 Merge함

/*  병합 정렬 알고리즘 */

   void Merge(int A[ ], int Low, int Mid, int High)
   /* 입력: A[Low:Mid], A[Mid+1:High] - 정렬된 두 배열 */
   /* 출력: A[Low:High]-A[Low:Mid]와 A[Mid+1:High]를  합병하여 정렬된 배열 */
             {
                  int B[NUM_OF_KEYS];
                  int i, LeftPtr, RightPtr, BufPtr;
/*1*/        LeftPtr = Low; RightPtr = Mid + 1; BufPtr = Low;
/*2*/        while(LeftPtr <= Mid && RightPtr <= High)
/*3*/               if(A[LeftPtr] < A[RightPtr])
/*4*/                    B[BufPtr++] = A[LeftPtr++];    
/*5*/               else B[BufPtr++] = A[RightPtr++];
/*6*/         if (LeftPtr > Mid)
/*7*/               for (i = RightPtr; i <= High; i++)
/*8*/                    B[BufPtr++] = A[i];
                 else    
/*9*/             for (i=LeftPtr; i <= Mid; i++)
/*10*/                  B[BufPtr++] = A[i];
/*11*/       for (i = Low; i <= High; i++)
/*12*/            A[i] = B[i];            
             }

②③④⑤줄의 while 루프는 머지가 진행되고 있는 두 부분배열 모두에 아직 키가 남아 있을 때, 이들을 머지

⑥⑦⑧⑨⑩줄의 if문은 두 부분배열 중에서 한 개의 배열에만 키가 남아 있을 때 이 키들을 배열 B의 머지된 원소들 뒤에 그대로 복사하는 일

⑪⑫ for루프는 머지가 끝나면 배열 B에 있는 정렬된 키들을 배열 A에 옮기는 일을 담당
-------------------------------------------------------------------------------

■ 병합 정렬 분석
▷ 원소의 개수가 각각 m,n인 두 배열을 합병하기 위하여는 최악의 경우에 m+n-1회의 비교
▷ 두 부분 배열의 크기가 같고 이를 m이라 할 때, 최악의 경우에 2m-1회의 비교
▷ n개의 원소로 구성된 배열에 병합 정렬을 적용하면 그 실행 시간은 n/2개의 원소로 된
           두 개의 부분 배열을 정렬하는 시간과 이들을 합병하는 데 드는 시간의 합으로 O(nlogn)
▷ 병합 정렬에서는 동일한 두 키의 상대 위치가 정렬 과정에서 변하지 않으므로 안정적이나,
           합병하는 과정에서 입력 배열의 크기만큼의 메모리 공간이 요구되므로 제자리 정렬은 아님
▷ 최악의 경우의 실행시간이 이지만 각 부분배열을 합병 과정에서 합병된 결과가 배열 B에서
           배열 A로 항상 복사되어야 하는 단점

자료 출처 : http://www.dreamy.pe.kr/zbxe/codeclip/5947

1) Max_Heapify(A, i)

l <- Left(i)
r <- Right(i)
//아래 코드는 부모와 두 자식 노드, 3개 중에서 largest값을 찾는다.
if i <= heap_size[A] and A[l] > A[i]
   then largest <- l
   else largest <- i
if r <= heap_size[A] and A[r] > A[largest]
   then largest <- r
//부모 노드가 제일 큰 값이 아닐경우 l, r 중에 largest로 지정된 값과 교환 후 recursive하게 아래로 진행
if largest != i
   then exchange A[i] <-> A[largest]
      Max_Heapify(A, largest)

2) Buiding a Max_Heap

heap_size[A] <- length[A]
//└length[A]/2┘ == 마지막 노드의 부모 노드에서부터라는 뜻 Leaf를 제외한 마지막 노드
for i <- └length[A]/2┘ downto 1
   do Max_Heapify(A, i)

3) Heap_Sort
- 위의 두가지 코드를 이용하여 구현
- 초기에 Max_Heap으로 만든 후 노드값 i와 root노드의 값을 서로 바꾸면서 1에 대해서만 Max_Heapify를 해주게되면 계속해서 Max_Heap의 형태를 유지하게 된다.

Buiding a Max_Heap(A)
for i <- length[A] downto 2
   do exchange A[1] <-> A[i]
      heapsize[A] <- heapsize[A]-1
      Max_Heapify(A, 1)

#include<stdio.h>
#define MAX 10
#define LOOP(A,B) for(i=A;i<B;i++)

void heapify( int [] , int );
void heapsort( int [] , int );

void main()
{
  int i, list[MAX];
  clrscr();

  printf("Randomized list is :\n");
  LOOP(0,MAX)
  list[i]=rand()/100;

  LOOP(0,MAX)
  printf("%8d",list[i]);

  LOOP(0,MAX)
  heapify(list,i);

  printf("\n\nHeapified list is :\n");
  LOOP(0,MAX)
  printf("%8d",list[i]);

  heapsort(list,MAX-1);

  printf("\nSorted list is :\n");
  LOOP(0,MAX)
  printf("%8d",list[i]);

}

//Convert any random array to heap array
void heapify ( int list[] , int newnode )
{
  int done=0, dad, temp;
  dad = ( newnode - 1 ) / 2;

  while( dad >= 0 && !done)
  {
    if(list[newnode] > list[dad])
     {
       temp = list[newnode];
       list[newnode]=list[dad];
       list[dad]=temp;
       newnode = dad;
       dad = dad/2;
     }
     else
     done = 1;

  }
}

void heapsort ( int list[] , int last )
{
   int i,temp;
   while(last > 0 )
   {
   temp = list[0];
   list[0]=list[last];
   list[last]= temp;
   LOOP(0,last)
   heapify(list,i);
   last--;
   }
}

void heapsort(int arr[], unsigned int N)
{
    int t; /* the temporary value */
    unsigned int n = N, parent = N/2, index, child; /* heap indexes */
    /* loop until array is sorted */
    for (;;) {
        if (parent > 0) {
            /* first stage - Sorting the heap */
            t = arr[--parent];  /* save old value to t */
        } else {
            /* second stage - Extracting elements in-place */
            n--;                /* make the heap smaller */
            if (n == 0) return; /* When the heap is empty, we are done */
            t = arr[n];         /* save lost heap entry to temporary */
            arr[n] = arr[0];    /* save root entry beyond heap */
        }
        /* insert operation - pushing t down the heap to replace the parent */
        index = parent; /* start at the parent index */
        child = index * 2 + 1; /* get its left child index */
        while (child < n) {
            /* choose the largest child */
            if (child + 1 < n  &&  arr[child + 1] > arr[child]) {
                child++; /* right child exists and is bigger */
            }
            /* is the largest child larger than the entry? */
            if (arr[child] > t) {
                arr[index] = arr[child]; /* overwrite entry with child */
                index = child; /* move index to the child */
                child = index * 2 + 1; /* get the left child and go around again */
            } else {
                break; /* t's place is found */
            }
        }
        /* store the temporary value at its new location */
        arr[index] = t;
    }
}

이 첨부 파일에 있는 건 일반적인 함수의 형태이다. (int형 뿐 아니라 모든 형태의 자료형을 비교할 수 있도록 만든 것이다)
자료 배열의 선두 번지인 base,
자료의 개수 nelem,
레코드의 크기 width,
키값의 비교를 하는 함수 포인터 fcmp 를 뜻한다.
fcmp 함수는
int intcmp(const void *a, const void *b) 등을 뜻한다.

■ 힙 정렬 개념
힙(heap)은 우선순위 큐(priority queue)의 일종으로 우선순위가 높은 요소를 효율적으로 관리하는 자료구조
힙은 배열 또는 연결리스트를 이용한 나무구조로 구현
힙은 부가적 메모리를 필요로 하지 않으며 매우 빠른 성능을 갖음
입력 자료에 무관하게 고른 성능을 보임
힙은 n개의 레코드로 구성된 입력 파일을 하나의 최대 힙(max heap) 즉, 각 노드에 저장되어 있는 원소의 값이 서브노드에 저장되어 있는 원소의 값보다 큰 전이진 트리 구조로 만드는 것
레벨 l 에서 노드의 수가 2l-1< n <2l+1 을 만족하여 레벨 l 상에서 모든 노드들은 가능하면 왼쪽의 위치에 존재하게 됨

■ 우선순위 큐(Priority Queue)

어떤 자료 구조를 의미하는 것이 아니라, 다만 스택 또는 큐 등을 이용하여 각각 우선순위를 갖는 자료를 관리하는 추상적인 개념

생성(construct) : N개의 자료로 우선순위 큐를 생성함
         생성 = N번의 삽입
삽입(insert) : 우선순위 큐에 새로운 자료를 삽입함
제거(remove) : 가장 높은 우선순위를 갖는 자료를 제거함
대치(replace) : 가장 높은 우선순위를 갖는 자료와 새로운 자료를 바꿈
         대치 = 제거 + 삽입
변경(change) : 우선순위 큐 내에 있는 자료의 순위를 변경함
         변경 = 삭제 + 삽입
삭제(delete) : 우선순위 큐 내에 있는 임의의 자료를 삭제함
결합(join) : 두개의 우선순위 큐를 결합하여 큰 우선순위 큐를 생성함

■ 힙(Heap)

키 값의 크기로 우선순위를 결정하는 자료구조
힙은 나무구조로 표현되는데, 이때 부모의 키 값은 반드시 두 자식의 키 값보다 작으면 않된다.
루트 노드에는 키 값이 가장 큰 자료가 위치하게 된다.
단말노드에 삽입된 자료는 우선순위를 맞추기 위해 상위 노드와 비교 후 교환되어져야 한다.

― 최단말 노드에 삽입된 자료는 부모와 비교된다.
― 큰 값을 갖는 경우 부모와 교체된다.
― 계속해서 상위에 있는 부모와 비교되고 크면 교체된다.

반대로 가장 큰 값을 갖는 루트 노드를 제거하는 경우

― 먼저 뿌리 노드의 자료를 제거한다.
― 뿌리 노드가 비어 있으므로 최단말 노드(min)의 자료를 임시로 뿌리에 옮긴다.
― 크기가 작은 노드(min)가 루트를 차지하고 있으므로 아래의 두 자식 노드중에서
   큰 값을 갖는 자료가 임시 자료(min)와 교체된다.
― 아래 레벨로 밀려난 임시 노드(min)는 또 다시 자식 노드와 비교되고 그중에서
   큰 값을 갖는 노드와 교체된다.
― 임시 노드(min)의 자식 노드가 더 작은 값을 갖는 곳 까지 반복 수행된다.

■ 배열로 트리 구현

연결리스트를 이용하면 부모 자식관계를 포인터로 직접 결합 가능
배열을 이용하게되면 첨자를 조작하여 간접적으로 연결해야 함
- 링크를 저장할 공간을 필요로하지 않는 장점을 가짐

- 불균형 트리의 경우 빈 노드를 위해서도 배열 공간을 확보해야 함

- 따라서 균형 트리(balanced tree)에 대해서 배열을 이용한다

힙은 균형 트리이므로 배열을 이용하는 것이 유리함 

■ 힙 정렬의 방법                                          

▷ 힙을 생성
- 힙의 크기를 배열의 크기로 하고 BuildHeap을 통해 힙조건에 맞게 수정하는 방식
- 배열에 저장은 초기 자료의 순서대로 힙이라 가정하고 트리로 구성함
― 부모 노드는 항상 두 자식 보다 큰 값을 가짐
- BuildHeap을 통해 하나씩 제자리를 찾아 내려보냄    

▷ 제거 동작을 반복 수행
― 가장 큰 값을 갖는 루트에서 제거 동작을 수행하고
― 루트가 없는 힙에서는 최단말 노드가 임시로 루트가 되며 제자리를 찾아 내려가게 됨
― 루트에서 뽑아낸 자료는 임의 배열에 끝에서부터 차례로 저장함

■ 힙 정렬 알고리즘
-------------------------------------------------------------------------------
#define LeftChild(i) (2*(i))

void PercDown (int A[ ], int i, int N)         /*  BuildHeap 수행*/
      {
            int Child, Temp;                           /*Temp는 루트의 값을 보관 */
/*1*/    for(Tmp=A[i]; LeftChild(i)<=N; i=Child)
            {
/*2*/          Child=LeftChild(i);
/*3*/          if(Child!=N && A[Child+1] > A[Child])
/*4*/              Child++;
/*5*/          if( Temp<A[Child])                /*  루프를 돌면서 루트의 값이 */
/*6*/              A[i]=A[Child];                  /*  자기의 위치로 내려옴  */
                  else
/*7*/               break;
            }
/*8*/    A[i]=Temp;
      }

void Heapsort(int A[ ],int N)
       {
               int i;
/*a*/       for( i  = N/2; i > 0; i--)           /*  BuildHeap 호출*/
/*b*/           PercDown(A, i, N);
/*c*/       for( i = N;  i >= 2; i--)
               {
/*d*/          Swap(&A[1], &A[i]);         /* DeleteMax  루트의 값을 제일 뒤로  */
/*e*/          PercDown(A, 1, i-1);         /* 제일 뒤에 있던 값이 루트에서 자기 위치로 */
               }                                           /*  BuildHeap 호출*/
        }
-------------------------------------------------------------------------------  

■ 성능

▷ MaxHeap을 만들어서 DeleteMax를 반복 수행하여 정렬
▷ N을 입력 파일의 크기라 하면 BuildHeap O(N),  N번 DeleteMax O(NlogN)
▷ BuildHeap은 내부노드(총 N/2개)에서만 수행되면 됨
- 단말노드는더이상내려갈곳이없으므로을적용할필요가없음
- N/2 노드(마지막 내부노드 위치)부터 뿌리 노드까지만 적용되면 됨
- 적용 범위가 반으로 줄었기 때문에 성능면에서 크게 향상된다. O(NlogN)
▷ 이론적으로 이상적인 O(NlogN)이나 실제 수행시간 길다.
▷ 뛰어난 성능을 가지면서도 추가적인 메모리를 필요로 하지 않음

자료 출처 : http://www.dreamy.pe.kr/zbxe/codeclip/5944

Heap Sort의 구조

Array & Heap

Heap의 자료 추가

Heap에서의 자료추가는 위의 그림과 같다. Heap 그 자체의 그림만으로 보면 굉장히 쉽지만 메모리 상에서 표현되었을 때는 다음과 같은 법칙을 따른다.

자료 추가는 가장 뒷부분에 되는데, 그 추가된 자료의 순서가 위와 같은 6번째라고 한다면 6에서 2를 나눈 순서의 값과 비교를 한다. 위의 그림에서는 70이 6번째로 추가 되었는데 3번째인 30과 비교했을때 70이 크기에 70과 30의 순서를 바꿔준다. 그리고 3번째로 온 70은 다시 2로 나누어진 순서인 1번째인 60과 비교를 한다. 60보다 70이 더 크니 이번에도 그 것을 바꾸어준다. 이렇게 하여 최대값 heap의 상태를 유지하는 것이다.

Botton up & Top down

Heap Sort에는 heap로의 변환을 사용할 경우에 노드 i가 자신의 조상 노드와 비교되면서 제자리를 찾는 모습을 가진 경우와 노드 i가 자신을 뿌리로 하는 작은 히프에 아래로 내려가면서 제자리를 찾는 경우가 있다.

첫 번째 경우를 Top down(하향식)이라고 하며 그 그림은 왼쪽과 같다. 꼭대기에서 바닥으로 간다는 것이다. 그리고 두 번째의 경우를 Bottom up(상향식)이라고 하는데, 말 그대로 바닥에서 꼭대기로 가는 꼴이다.

Heap Sort의 과정

위와 같은 정렬되지 않는 것을 최소값 heap으로 정렬하려고 한다.

최상위의 노드와 최하위의 노드를 변경한다.

80을 제외한 노드 중에서 가장 높은 값을

현재의 최상위 값인 50과 변경하는 작업을 수행한다.

여기에선 70과 50이 변경된다.

다시 tree에서 최상위인 70의 값을 최하위(6번째)의 수준인 30과 변경한다.

그리고 최상위의 자리로 가게된 30의 값과 70, 그리고 80을 제외한 값 중에

가장 큰 값인 60과 변경하는 작업을 수행한다.

그리고 역시나 마찬가지로 최상위에 있는 60과 최하위에 있는 20을 변경한다.

그런 다음 최상위 자리로간 20과 60, 70, 그리고 80을 제외한 값 중에

가장 큰 값인 50과 변경하는 작업을 수행한다.

이제 대충의 알고리즘은 감을 잡으셨을 것이다.

이번에도 최상위인 50과 최하위인 10을 변경하고,

남은 수 중에 가장 큰 값과 현재의 최상위인 10을 변경한다.

이전 작업으로 최상위 값이 된 30과 현재 최하위 값인 20을 변경한다.

그리고 역시 마찬가지로 변경된 최상위 값인 20과 남아 있는 값 중에 큰 값을 변경한다.

하지만 현재 변경이 되어진 20이 가장 큰 값이므로 이 경우에는 변경이 필요가 없다.

마지막으로 현재의 최상위 값인 20과 현재의 최하위 값인 10을 변경한다.

현재 tree 안에 남아 있는 노드는 10 하나 뿐이다.

변경할 노드는 더 이상 존재하지 않으므로 정렬이 끝난 것이다.

힙 정렬의 성능 특성

• 제자리 정렬(in place)이지만 불안정적이다.
• N 개의 원소를 정렬하는데 N log N 단계가 필요하다.
• 입력 배열의 순서에 민감하지 않다.
• 내부 루프가 퀵 정렬보다 약간 길어서 평균적으로 퀵 정렬보다 2배 정도 느리다.

힙 정렬 알고리즘(ADL)

HeapSort(a[])

n ← a.length - 1; // n은 히프 크기(원소의 수)

    // a[0]은 사용하지 않고 a[1 : n]의 원소를 오름차순으로 정렬한다.

for(i ← n / 2; i ≥ 1; i ← i - 1) do   // 배열 a[]를 히프로 변환한다.

heapify(a, i, n);                // i는 내부 노드

for(i ← n - 1; i ≥ 1; i ← i - 1) do { // 배열 a[]를 오름차순으로 정렬한다.

temp ← a[1]; // a[1]은 제일 큰 원소

a[1] ← a[i + 1]; // a[1]과 a[i + 1]을 교환한다.

a[i + 1] ← temp;

heapify(a, 1, i);

}

end heapsort

heapify(a[], h, m)
// 루트 h를 제외한 h의 왼쪽 서브트리와 오른쪽 서브트리는 히프이다.
// 현재 시점으로 노드의 최대 레벨 순서 번호는 m이다.

v ← a[h];

for(j ← 2 * h; j ≤ m; j ← 2 * j) do {

if(j < m and a[j] < a[j + 1])

then j ← j + 1; // j는 값이 큰 왼쪽 또는 오른쪽 자식 노드이다.

if(v ≥ a[j])

then exit;

else

a[j / 2] ← a[j]; // a[j]를 부모 노드로 이동시킨다.

}

a[j / 2] ← v;

end heapify()

힙 정렬 알고리즘(C)

void HeapSort(int A[], int n) {
/* 입력 : A[0 : n - 1] - 정렬할 배열, n - 정렬할 원소의 개수.

    출력 : A[0 : n - 1] - 정렬된 배열. */

int i;

for(i = n / 2; i > 0; i--)

MakeHeap(A, i - 1, n - 1);

for(i = n - 1; i > 0; i--) {

Swap(&A[0], &A[i]);

MakeHeap(A, 0, i - 1);

}

}

void MakeHeap(int A[], int Root, int LastNode) {
/* 입력 : A[Root : LastNode] - 히프로 변환할 배열. 입력 당시에는 이미 히프 구조이다.
            A[Root + 1 : LastNode]
    출력 : A[Root : LastNode] - 최대값 히프 */

int Parent, LeftSon, RightSon, Son, RootValue;

Parent = Root;

RootValue = A[Root];

LeftSon = 2 * Parent + 1;

RightSon = LeftSon + 1;

while(LeftSon <= LastNode) {

if(RightSon <= LastNode && A[LeftSon] < A[RightSon])

Son = RightSon;

else

Son = Leftson;

if(RootValue < A[Son]) {

A[Parent] = A[Son];

Parent = Son;

LeftSon = Parent * 2 + 1;

RightSon = LeftSon + 1;

}

else

break;

}

A[Parent] = RootValue;

}

작업한 숫자 쉘 정렬 파일인 ShellSort.C 첨부