지나간 삶

■ 힙 정렬 

힙정렬의 `힙(Heap)`인 이유는 힙(Heap)이라는 자료구조를 사용하기 때문이다. 힙은 기본적으로 이진트리 구성이며, 이 이진트리에 몇 가지 속성을 부여한 것이 힙이 된다. 

다음은 힙의 한 예로서 배열과 이진트리의 관계를 보여준다. 

  힙을 정의하자면 자식노드의 값보다 부모노드의 값이 같거나 큰, 완전 이진트리를 말한다. 즉 어떤 리스트가 힙으로 구성될 수 있다면 배열 상에서 인덱스 1에 해당하는 값인 뿌리노드의 값은 전체 노드의 값들보다 큰 특징을 갖는다.

 힙 정렬의 과정을 요약하면 다음과 같다. 

1. 리스트[배열]를 힙(Heap)으로 만든다.

2. 힙 상에서 정렬을 수행한다. 

우선 리스트를 힙으로 만드는 과정에서는 좌 하위트리와 우 하위트리가 각각 힙인 경우에 뿌리 노드의 재귀적인 이동을 통해 전체 트리를 힙으로 만드는 알고리즘이 사용된다. 즉, 끝 노드들은 그 자체로 힙이기 때문에 끝 노드를 자식노드로 가지는 노드들로부터 위의 알고리즘을 사용해 힙으로 만들면서 차례로 위로 올라오면서 전체가 힙의 구성이 완성 되어진다. 

그림으로 도식하면 다음과 같다.

 다음으로 힙 구조상에서 정렬하는 방법을 살펴보면, 힙은 뿌리노드의 값이 가장 크기때문에, 일단 정렬의 가장 기본이 되는 사항이 완성되어 있는 셈이다. 이 뿌리노드를 저장하고, 리스트 상의 맨 마지막 노드를 뿌리노드로 옮긴다. 이렇게 하면 이 노드는 뿌리노드만 힙이 아니고 좌 하위트리나 우 하위트리가 모두 힙이 된다.    여기에 힙 구조로 만드는 알고리즘을 적용하면 다시 뿌리노드의 값이 가장 큰 값이 된다. 그렇게 되면 이 뿌리노드의 값을 저장하고 다시 마지막 원소를 뿌리노드로 옮긴다. 이 과정을 반복하면 가장 큰 값부터 차례대로 찾아낼 수 있다. 

다음은 처음 두 개의 원소만 찾아내는 과정을 보인다.

void adjust(int *list, int i, int n)

/* i : adjust 알고리즘을시작하는노드의인덱스*/

/* n : 전체노드의개수*/

{

     int j, k, done;

     done = 0; // 아직끝나지않았음을표시

     k = list[i]; // 뿌리노드값, 즉옮겨야할원소의값

     j = 2 * i; // i 노드의좌자식노드

     while(( j <= n ) && (!done)) // 자식노드가있고not done 일때까지반복

     {

          if ( j < n )  // j + 1 < = n 과마찬가지로우자식노드의존재를검사

             if (list[j] < list[j+1])

                j = j + 1;  // 자식노드들중큰노드를선택

          if ( k >= list[j] )

             done = 1; // 자식노드보다크므로수행을중단

          else {

             list[j / 2] = list[j]; // 자식노드를부모노드로끌어올림

                                      // 자식노드에k값을쓰지않는이유는나중에

                                     // 수행이다끝난다음에쓰기때문

             j = 2 * j;

          }

     }

     list[ j / 2] = k; // 수행이끝나면찾아낸위치에맨처음저장한뿌리노드의값을저장

}

 void heap_sort(int *list, int n)

{

     int i, temp;

     for ( i = (n / 2) ; i >= 1 ; i-- ) // 초기힙만들기

         adjust(list, i, n);

     for ( i = (n - 1) ; i >= 1 ; i-- ) // 힙정렬의두번째단계

     {

         temp = list[i + 1];  // 마지막노드와뿌리노드의교환

         list[i + 1] = list[1];

         list[1] = temp;

         adjust(list, 1, i);  // i개의키에대하여adjust 적용

     }
}

이상으로 자주 사용되는 정렬법들을 알아보았는데 알고리즘별 속도를 간략히 도시하면 다음과 같다.