MySilpir.Net

/* 히프 정렬 알고리즘
HeapSort(a[])
	n ← a.length - 1;	// n은 히프 크기(원소의 수)
			// a[1 : n]의 원소를 오름차순으로 정렬
			// a[0]은 사용하지 않음
	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[]를 오름차순으로 정렬
		swap(a, 1, i+1);	// a[1]과 a[i+1]을 교환
       	heapify(a, 1, i);
   }
end heapSort()

heapify(a[], h, m)	// 노드의 최대 레벨 순서 번호는 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()
*/

/* sort.h */

const int TRUE = 1;
const int FALSE = 0;

inline void swap(int a[], int i, int j)
{
	int t = a[i]; a[i] = a[j]; a[j] = t;
}

void CheckSort(int a[], int n)
{
	int i, Sorted;
	Sorted = TRUE;

	for (i=1; i < n; i++)
	{
		if (a[i] > a[i+1]) Sorted = FALSE;
		if (!Sorted) break;
	}
	if (Sorted) cout << "정렬완료." << endl;
	else cout << "정렬 오류 발생." << endl;
}

#include <iostream.h>
#include <time.h>
#include <stdlib.h>
#include "sort.h"

const int N = 100000;

void heapify(int a[], int h, int m)
{
	int j, v;
	v = a[h];
	for (j=2*h; j <= m; j *= 2)
	{
		if (j < m && a[j] < a[j+1]) j++;
		if (v >= a[j]) break;
		else a[j/2] = a[j];
	}
	a[j/2] = v;
}

void HeapSort(int a[], int n)
{
	int i;
	for (i=n/2; i >=1; i--)
		heapify(a, i, n);
	for (i=n-1; i >=1; i--) {
		swap(a, 1, i+1);
		heapify(a, 1, i);
	}
}

void main()
{
	int i, a[N+1];
	double start_time;

	srand(time(NULL));
	for (i=1; i <= N; i++) a[i] = rand();

	start_time = clock();
	HeapSort(a, N);
	cout << "히프 정렬의 실행 시간 (N = " << N << ") : " << clock() - start_time << endl;
	CheckSort(a, N);
}