■ 힙 정렬
힙정렬의 `힙(Heap)`인 이유는 힙(Heap)이라는 자료구조를 사용하기 때문이다. 힙은 기본적으로 이진트리 구성이며, 이 이진트리에 몇 가지 속성을 부여한 것이 힙이 된다.
다음은 힙의 한 예로서 배열과 이진트리의 관계를 보여준다.
힙을 정의하자면 자식노드의 값보다 부모노드의 값이 같거나 큰, 완전 이진트리를 말한다. 즉 어떤 리스트가 힙으로 구성될 수 있다면 배열 상에서 인덱스 1에 해당하는 값인 뿌리노드의 값은 전체 노드의 값들보다 큰 특징을 갖는다.
힙 정렬의 과정을 요약하면 다음과 같다.
1. 리스트[배열]를 힙(Heap)으로 만든다.
2. 힙 상에서 정렬을 수행한다.
우선 리스트를 힙으로 만드는 과정에서는 좌 하위트리와 우 하위트리가 각각 힙인 경우에 뿌리 노드의 재귀적인 이동을 통해 전체 트리를 힙으로 만드는 알고리즘이 사용된다. 즉, 끝 노드들은 그 자체로 힙이기 때문에 끝 노드를 자식노드로 가지는 노드들로부터 위의 알고리즘을 사용해 힙으로 만들면서 차례로 위로 올라오면서 전체가 힙의 구성이 완성 되어진다.
그림으로 도식하면 다음과 같다.
다음으로 힙 구조상에서 정렬하는 방법을 살펴보면, 힙은 뿌리노드의 값이 가장 크기때문에, 일단 정렬의 가장 기본이 되는 사항이 완성되어 있는 셈이다. 이 뿌리노드를 저장하고, 리스트 상의 맨 마지막 노드를 뿌리노드로 옮긴다. 이렇게 하면 이 노드는 뿌리노드만 힙이 아니고 좌 하위트리나 우 하위트리가 모두 힙이 된다. 여기에 힙 구조로 만드는 알고리즘을 적용하면 다시 뿌리노드의 값이 가장 큰 값이 된다. 그렇게 되면 이 뿌리노드의 값을 저장하고 다시 마지막 원소를 뿌리노드로 옮긴다. 이 과정을 반복하면 가장 큰 값부터 차례대로 찾아낼 수 있다.
다음은 처음 두 개의 원소만 찾아내는 과정을 보인다.
다음은 전체적으로 힙정렬되는 과정을 예를 보인다.
힙 정렬은 퀵 정렬과는 달리 수행성능이 매우 나빠지는 입력형태가 없으며, 합병정렬과는 달리 별도의 기억공간을 필요로 하지 않는다.[평균 수행시간 n log n 을 갖는다]
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 적용
}
}
이상으로 자주 사용되는 정렬법들을 알아보았는데 알고리즘별 속도를 간략히 도시하면 다음과 같다.
