[Algorithm]Bubble sort, Insert sort, Select sort

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

#ifndef _DOL9_SORT_H_
#define _DOL9_SORT_H_

#include <stdio.h>
#include <stdlib.h>

#ifdef TEST
#define LOG(x)  (printf x)
#else
#define LOG(x)
#endif

int sort_init(char *data_type);
void print_data(void *data, int data_size);


int bubble_sort(void *data, int data_size);
int insert_sort(void *data, int data_size);
int select_sort(void *data, int data_size);

#endif

 

 

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