[출처 : http://dhdhks11.tistory.com/entry/Heap-Sort]



Heap Sort(힙 정렬)이란, 우선 순위 큐의 일종인 heap(히프)를 이용하는 정렬을 말한다. 정렬할 원소를 모두 공백 Heap(히프)에 하나씩 삽입하고 삭제 시에는 제일 큰 한 원소가 삭제가 된다. 이 원소를 리스트의 뒤에서부터 차례로 삽입하고 오른차순으로 리스트를 정렬한다.
Heap Sort의 구조



Heap는 완전 이진 나무(complete binary tree)로서 나무의 각 노드의 값은 그 노드가 자식 노드를 갖는 경우에 자식의 값보다 크거나 같아야 한다. 각 노드의 값이 자식 노드의 값보다 작거나 같도록 히프를 구성할 수도 있는데 이러한 히프를 최소값 히프(minheap)라고 하고, 각 노드의 값이 자식 노드의 값보다 크거나 같은 히프를 최대값 히프(maxheap)라고 한다.

(a)와 (c)는 heap이다. (b)는 완전 이진 나무가 아니고, (c)는 10이 3의 자식으로 되어있기 때문에 heap가 아니다.
Array & Heap




실제로 컴퓨터에서 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 첨부
저작자표시

+ Recent posts

티스토리툴바