ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [Algorithm] Heap sort
    개발하면서/Algorithm,Data Structure 2011.02.28 21:32


    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;
    		}
    	}
    }
    


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


    댓글 0

Designed by Tistory.