달력

122018  이전 다음

  •  
  •  
  •  
  •  
  •  
  •  
  • 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
  •  
  •  
  •  
  •  
  •  
merge sort의 기본 개념은 아래 그림과 같습니다.
사용자 삽입 이미지


정렬되지 않은 데이타가 들어오면 쪼갤수 없을때까지 쪼갠다음에 합치면서 정렬을 해나가는 알고리즘입니다.
대부분 예제 소스에는 재귀함수로 merge sort를 구현했는데요.  재귀함수로 안해도 되지않을까.....
라는 생각이 시작이었습니다.

쪼갤수 없을때까지 쪼개는과정이 불필요하다는 생각이 들었고, 그래서 제가 구현한 소스에는
처음부터 끝까지 돌면서
처음에는 두개씩 정렬, 그 다음에는 네개, 그 다음에는 8개.
이런식으로 정렬을 수행합니다.  재귀함수를 안쓰다보니 추가 메모리가 필요하네요;;(안쓰고도 가능한게 있으면 알려주세요)
아래는 구현한 소스입니다.


Posted by 오산돌구
기존에 작성되어있는것을 지우고 다시 쓰려고 했지만, 내가 얼마나 초짜인지 각성하기위해 새롭게 포스팅을 합니다.
맨처음 작성한 소스 부끄러운 내소스 입니다.
기존에 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 오산돌구