[Algorithm] Heap sort

Heap sort란 Heap 자료구조를 이용해서 sort하는 방법입니다.

우선 Heap에 대해 알아야겠죠?
http://dol9.tistory.com/129 전에 포스팅한게 있네요 : )

root에는 max값 혹은, min값이 있습니다.

정렬이 안된 데이타를 heap 구조로 만들고, root의 값 하나꺼내고 heap구조 재정렬하고
root의 값 하나꺼내고 정렬하고, 이를 반복하면 정렬된 데이타가 생성됩니다.

단순한 방법이네요;;;

 

아래는 지금 두줄 설명한것을 코딩한것입니다. 

생각한것을 막힘없이 구현할수 있도록 많이 짜보고 피드백 받고 수정하는 일련의 과정을 반복해야겠지요...

// default max heap~!!
int heap_sort(void *data, int max, int data_size, cmp compare)
{
	int begin, last;
	int maxnode;
	void *bucket;
	int i, k, noneright;
	void *parent, *leftchild, *rightchild;
	void *lastnode;

	bucket = malloc(data_size*(max+1));


	memcpy(bucket+data_size, data, max*data_size);

	begin =  max / 2;

	rightchild = NULL;

	//제일 마지막 부모노드의 오른쪽 자식노드가 없을경우
	noneright = 0;
	if (max < begin*2+1) {
		if(compare(bucket+(begin*data_size), bucket+((begin*2)*data_size)) < 0) {
			memswap(bucket+(begin*data_size), bucket+((begin*2)*data_size), data_size);
			noneright = 1;
		}
	}

//그외에 노드는 maxheap의 공식처럼 변경
	for (i = begin-noneright; i > 0; i--) {
		parent = bucket+(i*data_size); leftchild = bucket+(i*2*data_size);
		rightchild = bucket+((i*2+1)*data_size);

		maxnode = maxthree(parent, leftchild, rightchild, compare);
		if (maxnode==1) {
			memswap(parent, leftchild, data_size);
			godown(bucket, bucket+(max*data_size), data_size, i*2, compare);
		}
		else if (maxnode==2) {
			memswap(parent, rightchild, data_size);
			godown(bucket, bucket+(max*data_size), data_size, i*2+1, compare);
		}
	int j;
	for(j = 1; j < max+1; j++) {
	printf("%d\t", *((int*)bucket+j));
	}
	printf("\n");
	}

	//heap구조로 된것을 하나씩 data로 옮기자~!!
	//root하나꺼내고 정렬하고 꺼내고 정렬하고, 반복
	lastnode = bucket+(max*data_size);
	for (i = 0; i < max; i++) {
		memmove(data+(i*data_size), bucket+data_size, data_size);
		memmove(bucket+data_size, lastnode, data_size);
		lastnode = lastnode - data_size;
		
		// 재정렬 하는부분
		godown(bucket, bucket+(max*data_size), data_size, 1, compare);
	}

	free(bucket);

	return 0;
}
int godown(void *heapnode, void *lastnode, int data_size, int index, cmp compare)
{
	int last, maxnode;
	void *parent, *leftchild, *rightchild;
	last = (lastnode-(heapnode+data_size))/data_size+1;

	while (index<=last) {
		parent = heapnode+(index*data_size); leftchild = heapnode+(2*index*data_size);	rightchild = heapnode+((2*index+1)*data_size);	
		if ((2*index)+1<=last && (2*index)<=last) {
			maxnode = maxthree(parent, leftchild, rightchild, compare);
			if (maxnode == 1) {
				memswap(parent, leftchild, data_size);
				index = index * 2;
			}
			else if (maxnode==2) {
				memswap(parent, rightchild, data_size);
				index = index * 2 + 1;
			}
			else
				index = index * 2;
		}
		else if ((2*index)+1>last && (2*index)<=last) {
			maxnode = maxthree(parent, leftchild, NULL, compare);
			if (maxnode==1) {
				memswap(parent, leftchild, data_size);
				index = index * 2;
			}
			else
				index = index * 2;
		}
		else
			index = index * 2;
	}
	return 0;
}

// max return :   0-> parent,  1->left,  2->right
int maxthree(void *parent, void *left, void *right, cmp compare)
{
	void *max;

	if (right==NULL) {
		max = parent;
		if (compare(max, left) > 0)
			return 0;
		else
			return 1;
	}
	else {
		max = parent;
		if (compare(max, left) > 0) {
			if (compare(max, right) > 0)
				return 0;
			else
				return 2;
		}
		else {
			max = left;
			if (compare(max, right) > 0)
				return 1;
			else
				return 2;
		}
	}
}

실용주의 개발자를 향해 부단히 노력해야겠습니다.