달력

062018  이전 다음

  •  
  •  
  •  
  •  
  •  
  • 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
기존에 작성되어있는것을 지우고 다시 쓰려고 했지만, 내가 얼마나 초짜인지 각성하기위해 새롭게 포스팅을 합니다.
맨처음 작성한 소스 부끄러운 내소스 입니다.
기존에 DATA_TYPE을 한 이유가 대입과 swap때문에 했는데, 그럴필요없이, memxxx함수를 이용해 가능하다는것을 알고,
(qsort에서 그렇게 하는것을 보고) 다시 짜보았습니다. 와.....너무좋다. 이렇게 간단한걸, 노가다로 짠 내자신이....흑흑
main.c dol9_sort.h dol9_sort.c
Posted by 오산돌구
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");
}
Posted by 오산돌구
문자열 S, P가있고, S에서 P를 검색한다고 할때, 가장 기초적인건 아래와 같이 검색을 합니다.




비효율적인부분이 있습니다.  그래서 Knuth, Morris, Pratt 세 사람이 만든 KMP 알고리즘을 지금 설명하려고 합니다.

제가 이해한것을 풀어쓰는거라 잘못 이해한 것이 있을 수도 있습니다.
그럴때는 말씀해주시면 감사하겠습니다.

KMP는 패턴을 만들어서 검사에 실패했을때 다음 검사에서 불필요한 부분을 생략하는데 있습니다.
위 그림은 검사에 실패했을때 P를 오른쪽으로 한칸 이동하지만 KMP는 안해도 되는부분은 과감히 건너뜁니다.

KMP는 크게 나눠보면 찾고자하는 문자열에 패턴을 구하고 그 패턴을 이용해서 검사를 하는 것입니다.

문자열 페턴 구하는것을 설명하기에 앞서 suffix, prefix에 대해 알아봅시다.

문자열 abcdabc에 대한 suffix, prefix는

   prefix suffix
 1  a  c
 2  ab  bc
 3  abc  abc
 4  abcd  dabc
 5  abcda  cdabc
 6  abcdab  bcdabc
 7  abcdabc  abcdabc




3번 열을 보면 'abc', 'abc'같죠?  [ 마지막 전체 비교는 필요없는거죠....허허]
패턴을 찾는건 suffix와 prefix가 같은 부분을 찾는다고 할수 있습니다.

[a는 할필요가 없겠죠?]
ab, abc, abcd, abcda, abcdab, abcdabc에 대한 suffix, prefix가 같으면서 가장 긴~부분을 찾는 것이죠.


index 5, 문자 'b'를 예로 들면,
abcda까지 문자열 매칭이 됐는데, b에서 틀릴경우 1번째 문자로 이동하라는 얘기입니다.

1
 a
 a
2
 ab
 da
3
 abc
 cda
4
 abcd
 bcda
5
 abcda  abcda

첫번째문자 'a'와 마지막 문자 'a'가 같으니 이동해도 문제없겠죠?


6번째 문자 C의 경우, 매칭된 문자열은 abcab이고   최대 prefix, suffix는   ab이므로  2가 들어간것이죠~ : )
c,6이 실패했을때 진행방향이 틀렸네요;; d,3이 아니라 c,2로 이동하는게 맞습니다. 2010/12/01
틀렸는데도 아무 댓글이 없다는게 쓸쓸하네요......ㅠ,.ㅠ ㅋㅋ


소스는 아래와 같습니다.

Posted by 오산돌구

공부를 하면서 일을하면서 배운것들은 이젠 모두 이 블로그에 기록할겁니다.

결심했습니다. 자신의 지식을 공개하는건 손해가 아니라 더 이익이라는것을....

http://user.chollian.net/~chjeon12/exlibris/ex22.html


제나름대로 이해한것을 작성하는 부분이 많습니다. 틀린점이 있으면 지적해주시면 감사하겠습니다.

Posted by 오산돌구

초대장을 주신 그분 감사합니다.

이웃을 하고 싶어도 저 방법을 몰라 어떻게 하는지 모르겠네요 -_-;;

이글보신 초대장 주신분은 이웃 신청좀. . .

저희 흔적을 기록해볼까 합니다. 

잘 부탁 드려요~~

예전 블로그 : http://blog.naver.com/osanimma
Posted by 오산돌구