heap sort

heap-sort-test.c

// Heap 구조에 따라 출력 로직도 변경되어야 함 (1 ~ n까지만 출력)
void print_array(int a[], int n) {
	for (int i = 1; i <= n; i++) {
		printf("%3d", a[i]);
	}
}
 
void foo(int a[], int n) {
	printf("[Before] ");
	print_array(a, n);
	printf("\n[After ] ");
	heap_sort(a, n);
	print_array(a, n);
	puts("");	
}
 
int main() {
	printf("===Heap Sort===\n");
	int a[] = {INT_MAX, 2, 1, 3, 0, -1};
	int size = sizeof(a)/sizeof(int);
	foo(a, size-1);
 
	int b[] = {INT_MAX,2, 1, 4, 9, 5, 6, 8, 7};
	size = sizeof(b)/sizeof(int);
	foo(b, size-1);
 
	return 0;
}

heap-sort.c

void uphead(int a[], int k) {
	int v;
	v = a[k];
	a[0] = INT_MAX;
	while (a[k/2] <= v) {
		a[k] = a[k/2];
		k /= 2;
	}
	a[k] = v;
}
 
void downheap(int a[], int n, int k) {
	int i, v;
	v = a[k];
	while (k <= n/2) {
		i = k<<1;
		if (i < n && a[i] < a[i+1]) i++;
		if (v >= a[i]) break;
		a[k] = a[i];
		k = i;
	}
	a[k] = v;
}
 
void insert(int a[], int *n, int v) {
	a[++(*n)] = v;
	uphead(a, *n);
}
 
int extract(int a[], int *n) {
	int v = a[1];
	a[1] = a[(*n)--];
	downheap(a, *n, 1);
	return v;
}
 
void heap_sort(int a[], int n) {
	int i;
	int hn = 0;
	for (i = 1; i <= n; i++)
		insert(a, &hn, a[i]);
	for (i = hn; i >= 1; i--)
		a[i] = extract(a, &hn);
}