ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [Algorithm]Bubble sort, Insert sort, Select sort
    개발하면서/Algorithm,Data Structure 2010.12.24 10:35
    sort 세개를 한꺼번에 포스팅하는 이유는?
    세개 sort에 대해서는 자료가 너무 많아서 굳이 설명 하지 않아도 될 것같아서 였습니다.

    그럼 지금 왜 포스팅을 하냐?
    위 세개 알고리즘에 대한 소스를 공유하고자 입니다. 더 나은 방법이나 잘못된 부분이 있으면 알려주세요.
    지금 개념 파악후 혼자 낑낑대면서 하고있는데.....정말 제가 부족하다는걸 뼈저리게 느끼고 있습니다.

    int와 char을 지원하고 구조체 정렬까지 하려고 했는데 이 부분에 대해선 아직 머리가 안돌아가네요 허허허

    dol9_sort.c, dol9_sort.h main.c 로 구성되어있습니다.

    조금 수정한 내소스

    dol9_sort.h
    #include "dol9_sort.h"
    
    int main(int argc, char *argv[])
    {
    	//int input[10] = {3, 2, 5, 6, 1, 4, 8, 9, 7, 0};
    	char input[10] = {'d', 'c', 'e', 'b', 'w', 'z', 'q', 'x'};
    	int data_size;
    
    	data_size = 8;
    
    	sort_init("char");
    	//sort_init("Int");
    
    	print_data(input, data_size);
    
    	select_sort(input, data_size);
    
    	print_data(input, data_size);
    	
    	return 0;
    }
    
    dol9_sort.h dol9_sort.c
    #include "dol9_sort.h"
    #include <string.h>
    
    static short DATA_TYPE;
    
    int compare(void *data1, void *data2);
    void swapdata(void *data1, void *data2);
    
    
    int sort_init(char *data_type){
    	char t_data_type[10];
    	int i;
    	
    	if (strlen(data_type) > 9) {
    		printf("data_type error [char or int plz~~]\n");
    		return 1;
    	}
    
    	i = 0;
    	while(*data_type != '\0') {
    		if (*data_type > 96 && *data_type < 123) {
    			t_data_type[i] = (char)*data_type - 32;		
    		}
    		else if (*data_type > 64 && *data_type < 91) {
    			t_data_type[i] = (char)*data_type;
    		}
    		else
    			return 1;
    		data_type++;
    		i++;
    	}		
    	t_data_type[i] = '\0';
    
    	if (strcmp(t_data_type, "INT")==0) {
    		DATA_TYPE = 4;
    	}
    	else if (strcmp(t_data_type, "CHAR")==0) {
    		DATA_TYPE = 1;
    	}
    
    	return 0;
    }
    
    int bubble_sort(void *data, int data_size)
    {
    	int i, j;
    
    	for(i = 0; i < data_size-1; i++) {
    		for(j = 0; j < data_size-1; j++) {
    			if(compare((data+(j*DATA_TYPE)), (data+((j+1)*DATA_TYPE))) == 1) { 
    				swapdata((data+(j*DATA_TYPE)), (data+((j+1)*DATA_TYPE)));
    			}
    		}
    	}
    	return 1;
    }
    
    int select_sort(void *data, int data_size)
    {
    	int i, j;
    	int min, minidx;
    
    	minidx = 0;
    	if (DATA_TYPE == 4) {
    		for(i = 0; i < data_size-1; i++) {
    	min = 2147483647;
    			for(j = i+1; j < data_size; j++) {
    				if (compare(&min, ((int*)data+j+1)) == 1) {
    					minidx = j;
    					min = *((in*)data+j);
    				}
    			}
    			swapdata((int*)data+i, (int*)data+minidx);	
    		}
    	}
    	else if (DATA_TYPE == 1){
    		for(i = 0; i < data_size; i++) {
    	min = 127;
    			for(j = i; j < data_size; j++) {
    				if (compare(&min, ((char*)data+j)) == 1) {
    					minidx = j;
    					min = *((char*)data+j);
    				}
    			}
    			swapdata((char*)data+i, (char*)data+minidx);	
    		}
    	}
    	return 1;
    }
    
    int insert_sort(void *data, int data_size)
    {
    	int value, movesize;
    	int i, j;
    	
    	if (DATA_TYPE == 4) {
    		for (i = 1; i < data_size; i++) {
    			value = *(((int*)data)+i);
    			for(movesize=0, j = i; j > 0 && *(((int*)data)+j-1)>value; j--) {
    				movesize++;
    			}
    			if ( movesize ) {
    				memmove(data+j+1, data+j, movesize);
    				*((int*)data+j) = value;
    			}
    			*((int*)data+j) = value;
    		}
    	}
    	else if (DATA_TYPE == 1) {
    		for (i = 1; i < data_size; i++) {
    			value = *(((char*)data)+i);
    			for(movesize=0, j = i; j > 0 && *(((char*)data)+j-1)>value; j--) {
    				movesize++;
    			}
    			if ( movesize ) {
    				memmove(data+j+1, data+j, movesize);
    				*((char*)data+j) = value;
    			}
    		}
    	}
    	return 1;
    }
    
    int compare(void *data1, void *data2)
    {
    	int rvalue = 0;
    	if (DATA_TYPE == 4)
        	rvalue = *(int*)data1 > *(int*)data2 ? 1 : \
                              *(int*)data1 == *(int*)data2 ? 0 : -1;
    	else if (DATA_TYPE == 1)
    		rvalue = *(char*)data1 > *(char*)data2 ? 1 : \
                                         *(char*)data1 == *(char*)data2 ? 0 : -1;
    	
    	return rvalue;
    }
    
    void swapdata(void *data1, void *data2)
    {
    	int itemp;
    	char ctemp;
    
    	if (DATA_TYPE == 4) {
    		itemp = *(int*)data1;
    		*(int*)data1 = *(int*)data2;
    		*(int*)data2 = itemp;
    	}
    	else if (DATA_TYPE == 1) {
    		ctemp = *(char*)data1;
    		*(char*)data1 = *(char*)data2;
    		*(char*)data2 = ctemp;
    	}
    }
    
    
    void print_data(void *data, int data_size)
    {
        int i;
    	if (DATA_TYPE == 4) {
    		for (i = 0; i < data_size; i++) {
    			printf("input[%d] : %d\t", i, *(int*)(data+i));
    			if (i%3==0) {
    				printf("\n");
    			}
    		} 
    	}
    	else if (DATA_TYPE == 1) {
    		for (i = 0; i < data_size; i++) {
    			printf("input[%d] : %c\t", i, *(char*)(data+i));
    			if (i%3==0) {
    				printf("\n");
    			}
    		} 
    	}
    	printf("\n");
    }
    

    댓글 0

Designed by Tistory.