sort 함수들 범용성을 지니게 하기 (구현)

간단프로그래밍2009. 11. 28. 02:12

sort 함수들 범용성을 지니게 하기 (구현)

#include "sort.h"

void copy(void* a, void* b, int elem_size)
{
	char* desti = (char*)a;
	char* source = (char*)b; //char 형이면 1바이트 최소바이트 단위
	int i;
	for(i=0; i<elem_size; i++)
	{
		*desti = *source;    //b에서 a로 1바이트씩 원소 크기만큼 카피
		
		++desti;
		++source;
	}
}
void swap(void* a, void* b, int elem_size)
{
	char* desti1 = (char*)a;
	char* desti2 = (char*)b;
	char tmp;
	int i;
	for(i=0; i<elem_size; i++)
	{
		tmp = *desti1;
		*desti1 = *desti2;
		*desti2 = tmp;        //1 바이트씩 스왑

++desti1 , ++desti2;
	}
}
int equal(void* a, void* b, int elem_size)
{
	char* com1 = (char*)a;
	char* com2 = (char*)b;
	int i;
	for(i=0; i<elem_size; i++)
	{
		if(*com1 == *com2)
			++com1, ++com2;
		else
			return 0;
	}
	return 1;
}

//-----------insert sort ---------------//
void insert_sort(void* arr, int arr_size, int elem_size, int (*_compare)(const void* a, const void* b))
{
	int i,j;
	char* seq = (char*)arr;          //arr을 char형 포인터로 1바이트씩
	char* tmp = (char*)malloc(elem_size); //원소 사이즈만큼의 tmp 변수 동적 할당

for(i = 1; i < arr_size; i++)
	{
		copy(tmp,(seq + (i*elem_size)),elem_size);
		j = i - 1;
		while((j >= 0)&& (_compare(tmp,(seq+(j*elem_size)))))
		{
			copy((seq+((j+1)*elem_size)),(seq+(j*elem_size)),elem_size);
			j = j - 1;
		}
		copy((seq + ((j+1)*elem_size)), tmp, elem_size);
	}
	free(tmp);
}

//------------ quick sort ---------------------//
int partition(void* arr, int start, int end, int elem_size, int (*_compare)(const void* a, const void* b))
{
	char* seq = (char*)arr;
	char* key = (char*)malloc(elem_size);
	int i, pos = start;

copy(key, (seq+(start*elem_size)),elem_size);
	for(i = start + 1; i <= end; i++)
	{
		if(_compare((seq+(i*elem_size)),key))
		{
			pos = pos + 1;
			swap((seq+(pos*elem_size)),(seq+(i*elem_size)),elem_size);
		}
	}
	swap((seq+(start*elem_size)),(seq+(pos*elem_size)),elem_size);
	free(key);
	return pos;
}
void Q_sort(void* arr, int start, int end, int elem_size, int (*_compare)(const void* a, const void* b))
{
	int q;
	if(start < end)
	{
		q = partition(arr,start,end,elem_size,_compare);
		Q_sort(arr,start,q-1,elem_size,_compare);
		Q_sort(arr,q+1,end,elem_size,_compare);
	}
}
void quick_sort(void* arr, int arr_size, int elem_size, int (*_compare)(const void* a , const void* b))
{ //wrapper function
	Q_sort(arr,0,arr_size-1,elem_size,_compare);
}

//------------------merge sort---------------------------//

void merge(void* arr, int start, int mid, int end, int elem_size, int (*_compare)(const void* a, const void* b))
{
	char* seq = (char*)arr;

char* tmp = (char*)malloc(elem_size * (end-start + 1)); //local array
	
	int i,j, pos = start;
	for(i=0, j=start; i <(end - start + 1); i++, j++)  //copy local array
		copy((tmp + (i*elem_size)),(seq+(j*elem_size)),elem_size);
	
	i = start;
	j = mid+1;

while(i <= mid && j <= end)
	{
		if(_compare((tmp+((i-start)*elem_size)),(tmp+((j-start)*elem_size)))||
			equal((tmp+((i-start)*elem_size)),(tmp+((j-start)*elem_size)),elem_size))
		{
			copy((seq+(pos*elem_size)),(tmp+((i-start)*elem_size)),elem_size);
			i++;
		}
		else
		{
			copy((seq+(pos*elem_size)),(tmp+((j-start)*elem_size)),elem_size);
			j++;
		}
		pos++;
	}
	while(i <= mid)
	{
		copy((seq+(pos*elem_size)),(tmp+((i-start)*elem_size)),elem_size);
		i++;
		pos++;
	}
	while(j <= end)
	{
		copy((seq+(pos*elem_size)),(tmp+((j-start)*elem_size)),elem_size);
		j++;
		pos++;
	}
	free(tmp);
}
void M_sort(void* arr, int start, int end, int elem_size,int (*_compare)(const void* a, const void* b))
{
	int mid;
	if(start == end)
		return;
	
	mid = (start + end)/2;

M_sort(arr,start,mid,elem_size,_compare);
	M_sort(arr,mid+1,end,elem_size,_compare);

merge(arr,start,mid,end,elem_size,_compare);
}

void merge_sort(void* arr, int arr_size, int elem_size, int (*_compare)(const void* a, const void* b))
{ // wrapper function
	M_sort(arr,0,arr_size-1,elem_size,_compare);
}

//-------------heap sort-----------------------//

void heapify(void* arr, int root,int arr_size, int elem_size, int (*_compare)(const void* a, const void* b))
{
	char* seq = (char*)arr;
	int left = 2*root + 1, right = 2*root + 2  ,choose;

if(right <= arr_size)
	{
		if(_compare((seq+(left*elem_size)),(seq+(right*elem_size))))
			choose = left;
		else
			choose = right;
	}
	else if(left <= arr_size)
		choose = left;
	else 
		return ;
	if(_compare((seq+(choose*elem_size)),(seq+(root*elem_size))))
	{
		swap((seq+(choose*elem_size)),(seq+(root*elem_size)),elem_size);
		heapify(arr,choose,arr_size,elem_size,_compare);
	}
}

void build_heap(void* arr, int arr_size, int elem_size, int (*_compare)(const void* a, const void* b))
{
	int i;
	for(i = arr_size / 2; i >= 0; i--)
		heapify(arr,i,arr_size,elem_size,_compare);
}

void heap_sort(void* arr, int arr_size, int elem_size, int (*_compare)(const void* a, const void* b))
{
	int i;
	char* seq = (char*)arr;
	build_heap(arr,arr_size,elem_size,_compare);
	for(i=arr_size; i > 0; i--)
	{
		swap((seq+(0*elem_size)),(seq+(i*elem_size)),elem_size);
		heapify(arr,0,i-1,elem_size,_compare);
	}
}

copy 나 swap은 내부적으로

char* 로 하여

가리키는 값이 1바이트씩 가리키게 만들었고

어떤 자료형이든 입력된 원소의 바이트크기 만큼 수행할수 있도록 한것인데

좀 꼼수로 한거 같은 느낌이 든다.

저작자표시

'간단프로그래밍' 카테고리의 다른 글

floating point (0)	2010.04.12
BIG INT 그리고 팩토리얼 (0)	2010.03.06
strlen, strcpy, strcat, strcmp 구현해보기 (2)	2009.12.04
sort 함수들 범용성을 지니게 하기 (사용예) (0)	2009.11.28
sort 함수들 범용성을 지니게 하기 (구현) (0)	2009.11.28
sort 함수들 범용성을 지니게 하기 (0)	2009.11.28

Posted by 멍충한아싸

Trackback 0 Comment 0

댓글을 달아 주세요

«이전 1 ··· 11 12 13 14 15 16 다음»

일	월	화	수	목	금	토
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30
31

성대아싸의 멍충한 프로그래밍