[출처 : http://inthechaos.tistory.com/entry/탐색-SearchMainc]




#pragma warning(disable:4996)
#include <stdio.h>
#include <stdlib.h>
#include "Search.h"
//상수 정의
enum { ARRAY_SIZE = 100, MAX_VALUE = 1000 };
void fillArray(int *array, int size);
void printArray(const int *array, int size);
int compare(const void *p1, const void *p2);
void main(void)
{
 int array[ARRAY_SIZE];
 int value, pos;
 fillArray(array, ARRAY_SIZE);
 printArray(array, ARRAY_SIZE);
 //순차 탐색
 printf("[순차 탐색]\n");
 while(1)
 {
  printf("입력 : ");
  scanf("%d", &value);
  if(value < 0 || value >= MAX_VALUE)
  {
   break;
  }
  pos = linearSearch(array, ARRAY_SIZE, value);
  printf("결과 : %s\n\n", (pos != -1) ? "성공" : "실패");
 }
 printf("\n\n");
 //정렬
 qsort(array, ARRAY_SIZE, sizeof(array[0]), compare);
 printArray(array, ARRAY_SIZE);
 //이진 탐색
 printf("[이진 탐색]\n");
 while(1)
 {
  printf("입력 : ");
  scanf("%d", &value);
  if(value < 0 || value >= MAX_VALUE)
  {
   break;
  }
  pos = linearSearchSort(array, ARRAY_SIZE, value);
  printf("순차 : %s\n\n", (pos != -1) ? "성공" : "실패");
  pos = binarySearch(array, ARRAY_SIZE, value);
  printf("이진 : %s\n\n", (pos != -1) ? "성공" : "실패");
 }
}
void fillArray(int *array, int size)
{
 int i;
 for(i=0; i<size; i++)
 {
  array[i] = rand() % MAX_VALUE;
 }
}
void printArray(const int *array, int size)
{
 int i;
 for(i=0; i<size; i++)
 {
  printf("%3d ", array[i]);
  if(i%10 == 9)
  {
   printf("\n");
  }
 }
 printf("\n\n");
}
int compare(const void *p1, const void *p2)
{
 return *(int*) p1 - *(int*) p2;
}

저작자표시
[출처 : http://inthechaos.tistory.com/entry/탐색-Searchh-Searchc]


Search.h

//선언
int linearSearch(int *array, int size, int value);
int linearSearchSort(int *array, int size, int value);
int binarySearch(int *array, int size, int value);





Search.c

#pragma warning(disable:4996)
#include <stdio.h>


int linearSearch(int *array, int size, int value)
{
 int i;
 for(i=0; i<size; i++)
 {
  if(array[i] == value)
  {
   printf("횟수 : 성공[%d번]\n", i);
   
   return i;
  }
 }
 printf("횟수 : 실패[%d번]\n", i);
 
 return -1;
}
int linearSearchSort(int *array, int size, int value)
{
 int i;
 for(i=0; i<size; i++)
 {
  if(array[i] >= value)
  {
   if(array[i] == value)
   {
    printf("횟수 : 성공[%d번]\n", i);
    return i;
   }
   else
   {
    break;
   }
  }
 }
 printf("횟수 : 실패[%d번]\n", i);
 return -1;
}
int binarySearch(int *array, int size, int value)
{
 int i, left, right, middle;
 left = 0, right = size-1;
 for(i=0; left<=right; i++)
 {
  middle = (left+right) / 2;
  if(array[middle] == value)
  {
   printf("횟수 : 성공[%d번]\n", i);
   return middle;
  }
  if(array[middle] < value)
  {
   left = middle+1;
  }
  else
  {
   right = middle-1;
  }
 }
  printf("횟수 : 실패[%d번]\n", i);
  return -1;
}

저작자표시
[출처 : http://inthechaos.tistory.com/entry/정렬-qsort]




 


#pragma warning(disable:4996)
#include <stdio.h>
#include <stdlib.h>
void printArray(int *array, int size);
int cmpAsc(const void *p1, const void *p2);
int cmpDsc(const void *p1, const void *p2);
void main(void)
{
 int array[11] = { 87, 41, 36, 71, 98, 56, 28, 45, 50, 11, 63 };
 
 printf("원본 : ");
 printArray(array, 11);
 qsort(array, 11, sizeof(array[0]), cmpAsc);
 printf("오름 : ");
 printArray(array, 11);
 qsort(array, 11, sizeof(array[0]), cmpDsc);
 printf("내림 : ");
 printArray(array, 11);
}
void printArray(int *array, int size)
{
 int i;
 for(i=0; i<size; i++)
 {
  printf("%d ", array[i]);
 }
 printf("\n");
}
int cmpAsc(const void *p1, const void *p2)
{
 return *(int*)p1 - *(int*)p2;
}
int cmpDsc(const void *p1, const void *p2)
{
 return cmpAsc(p2, p1);
}
저작자표시
[출처 : http://inthechaos.tistory.com/entry/정렬-SortMainc]



#pragma warning(disable:4996)
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include "Sort.h"



void fillArray(int *array, int size);
void printArray(const int *array, int size);
void bubbleTest(const int *array, int size);
void selectionTest(const int *array, int size);
void insertionTest(const int *array, int size);
void heapTest(const int *array, int size);
void mergeTest(const int *array, int size);
void quickTest(const int *array, int size);
void main(void)
{
 int *array=NULL;
 int i, size;
 srand((unsigned) time(NULL));
 //초기화
 size = 4096;
 array = malloc(size*128*sizeof(int));
 //저속 정렬
 printf("[저속 정렬]\n");
 for(i=0; i<4; i++)
 {
  fillArray(array, size);
  printf("개수 : %d\n", size);
  bubbleTest(array, size);
  selectionTest(array, size);
  insertionTest(array, size);
  printf("\n");
  size *= 2;
 }
 //고속 정렬
 printf("\n[고속 정렬]\n");
 for(i=0; i<4; i++)
 {
  fillArray(array, size);
  printf("개수 : %d\n", size);
  heapTest(array, size);
  mergeTest(array, size);
  quickTest(array, size);
  printf("\n");
  size *= 2;
 }
 free(array);
}
void fillArray(int *array, int size)
{
 int i;
 for(i=0; i<size; i++)
 {
  array[i] = rand() * rand();
 }
}
void printArray(const int *array, int size)
{
 int i;
 for(i=0; i<size; i++)
 {
  printf("%10d ", array[i]);
  if(i%7 == 6)
  {
   printf("\n");
  }
 }
 printf("\n");
}
void bubbleTest(const int *array, int size)
{
 clock_t start, end;
 int *temp;
 temp = malloc(size*sizeof(int));
 memcpy(temp, array, size*sizeof(int));
 start = clock();
 bubbleSort(temp, size);
 end = clock();
 printf("버블 : %.3f\n", (end-start) / (double) CLOCKS_PER_SEC);
 free(temp);
}
void selectionTest(const int *array, int size)
{
 clock_t start, end;
 int *temp;
 temp = malloc(size*sizeof(int));
 memcpy(temp, array, size*sizeof(int));
 start = clock();
 selectionSort(temp, size);
 end = clock();
 printf("선택 : %.3f\n", (end-start) / (double) CLOCKS_PER_SEC);
 free(temp);
}
void insertionTest(const int *array, int size)
{
 clock_t start, end;
 int *temp;
 temp = malloc(size*sizeof(int));
 memcpy(temp, array, size*sizeof(int));
 start = clock();
 insertionSort(temp, size);
 end = clock();
 printf("삽입 : %.3f\n", (end-start) / (double) CLOCKS_PER_SEC);
 free(temp);
}
void heapTest(const int *array, int size)
{
 clock_t start, end;
 int *temp;
 temp = malloc(size*sizeof(int));
 memcpy(temp, array, size*sizeof(int));
 start = clock();
 heapSort(temp, size);
 end = clock();
 printf("힙   : %.3f\n", (end-start) / (double) CLOCKS_PER_SEC);
 free(temp);
}
void mergeTest(const int *array, int size)
{
 clock_t start, end;
 int *temp;
 temp = malloc(size*sizeof(int));
 memcpy(temp, array, size*sizeof(int));
 start = clock();
 mergeSort(temp, size);
 end = clock();
 printf("합병 : %.3f\n", (end-start) / (double) CLOCKS_PER_SEC);
 free(temp);
}
void quickTest(const int *array, int size)
{
 clock_t start, end;
 int *temp;
 temp = malloc(size*sizeof(int)+4);
 temp[size] = INT_MAX;
 memcpy(temp, array, size*sizeof(int));
 start = clock();
 quickSort(temp, size);
 end = clock();
 printf("퀵   : %.3f\n", (end-start) / (double) CLOCKS_PER_SEC);
 free(temp);
}
저작자표시
[출처 : http://inthechaos.tistory.com/entry/정렬-Sortc]


#include <stdio.h> #include <malloc.h> #include "Sort.h"

 void swap(int *p1, int *p2) { int tmp; tmp = *p1; *p1 = *p2; *p2 = tmp; } //버블 정렬 void bubbleSort(int *array, int size) { int i; for(i=size; i>1; i--) { bubbleUp(array, i); } } void bubbleUp(int *array, int size) { int i; for(i=1; i<size; i++) { if(array[i-1] > array[i]) { swap(array+i-1, array+i); } } } //선택 정렬 void selectionSort(int *array, int size) { int i; for(i=size; i>1; i--) { selection(array, i); } } void selection(int *array, int size) { int i, max=0; for(i=1; i<size; i++) { if(array[i] > array[max]) { max = i; } } swap(array+max, array+size-1); } //삽입 정렬 void insertionSort(int *array, int size) { int i; for(i=2; i<=size; i++) { insertion(array, i); } } void insertion(int *array, int size) { int i, unsorted = array[size-1]; for(i=size-2; i>=0; i--) { if(unsorted >= array[i]) { break; } array[i+1] = array[i]; } array[i+1] = unsorted; } //힙 정렬 void heapSort(int *array, int size) { int i; for(i=size/2; i>=0; i--) { reheapDown(array, size, i); } for(i=size-1; i>0; i--) { swap(array, array+i); reheapDown(array, i, 0); } } void reheapDown(int *array, int size, int parent) { int left, right, max; while(1) { left = parent*2+1; right = parent*2+2; if(left >= size) { break; } if(left == size-1) { max = left; } else if(array[left] > array[right]) { max = left; } else { max = right; } if(array[parent] >= array[max]) { break; } swap(array+parent, array+max); parent = max; } } //합병 정렬 void mergeSort(int *array, int size) { if(size > 1) { mergeSort(array, size/2); mergeSort(array+size/2, size-size/2); merge(array, size/2, size); } } void merge(int *array, int middle, int size) { int i, left, right; int *temp = malloc(size*sizeof(int)); left = 0; right = middle; for(i=0; left<middle && right<size; i++) { if(array[left] <= array[right]) { temp[i] = array[left++]; } else { temp[i] = array[right++]; } } while(left < middle) { temp[i++] = array[left++]; } while(right < size) { temp[i++] = array[right++]; } for(i=0; i<size; i++) { array[i] = temp[i]; } free(temp); } //빠른 정렬 void quickSort(int *array, int size) { if(size > 1) { int pivot = split(array, size); quickSort(array, pivot); quickSort(array+pivot+1, size-pivot-1); } } int split(int *array, int size) { int pivot=array[0], left=1, right=size-1; while(1) { while(array[left] < pivot) { left++; } while(array[right] > pivot) { right--; } if(left >= right) { break; } swap(array+left, array+right); left++, right--; } swap(array, array+right); return right; }

저작자표시
[출처 : http://inthechaos.tistory.com/entry/정렬-Sorth]


//공통 함수
void swap(int *p1, int *p2);


void bubbleSort(int *array, int size);
void bubbleUp(int *array, int size);


void selectionSort(int *array, int size);
void selection(int *array, int size);


void insertionSort(int *array, int size);
void insertion(int *array, int size);


void heapSort(int *array, int size);
void reheapDown(int *array, int size, int parent);


void mergeSort(int *array, int size);
void merge(int *array, int middle, int size);


void quickSort(int *array, int size);
int split(int *array, int size);
저작자표시
[출처 : http://inthechaos.tistory.com/entry/해시-HashMainc]


#pragma warning(disable:4996) #include <stdio.h> #include <string.h> #include "Hash.h" void main(void) { const char *words[] = { "naver", "page", "web", "net", "black", "hand", "rain", "meal", "hi", "wow", "news", "movie", "car", "sky", "snow", "paper", "task", "air", "book", "2008", "red", "sound", "voice", "face", "mob", "girl", "miss", "hope", "sea", "apple", "man", "think", "smile", "hat", "door", "water", "claim", "venus", "music", "stop", "green", "gas", "wind", "house", "right", "no", "sorry", "mine", "tv", "cry", "boys", "scope", "dress", "star", "farm", "ever", "play", "piano", "gag", "child", }; int i, code; char key[WORD_SIZE]; init(); for(i=0; i<60; i++) { printf("%5s ", words[i]); insertKey(words[i]); if(i%10 == 9) { printf("\n"); } } printf("\n"); printHash(); while(1) { printf("delete key : "); scanf("%s", key); printf("code : %d\n", code = getHashCode(key)); printBucket(code); if(deleteKey(key) == 0) { break; } printBucket(code); printf("\n"); } }

저작자표시
[출처 : http://inthechaos.tistory.com/entry/해시-Hashc]



#pragma warning(disable:4996) #include <stdio.h> #include <string.h> #include "Hash.h" //해시 관련 정의 enum { BUCKET_COUNT = 7, BUCKET_SIZE = 512 }; typedef struct _BUCKET { int count; char bucket[BUCKET_SIZE][WORD_SIZE]; } BUCKET; static BUCKET g_hash[BUCKET_COUNT]; void init(void) { int i; for(i=0; i<BUCKET_COUNT; i++) { g_hash[i].count = 0; } } unsigned getHashCode(const char *s) { unsigned sum = 0; while(*s) { sum += *s++; } return sum%BUCKET_COUNT; } void insertKey(const char *s) { BUCKET *pb = g_hash + getHashCode(s); strcpy(pb->bucket[pb->count], s); pb->count++; } int deleteKey(const char *s) { BUCKET *pb = g_hash + getHashCode(s); int i; for(i=0; i<pb->count; i++) { if(strcmp(pb->bucket[i], s) == 0) { strcpy(pb->bucket[i], pb->bucket[--pb->count]); return 1; } } return 0; } const char *findKey(const char *s) { int i, code = getHashCode(s); for(i=0; i<g_hash[code].count; i++) { if(strcmp(g_hash[code].bucket[i], s) == 0) { return g_hash[code].bucket[i]; } } return NULL; } void printBucket(unsigned index) { BUCKET *pb = g_hash + index; int i; printf("%d[%2d] : ", index, pb->count); for(i=0; i<pb->count; i++) { printf("%s ",pb->bucket[i]); } printf("\n"); } void printHash(void) { int i; for(i=0; i<BUCKET_COUNT; i++) { printBucket(i); } printf("\n"); }

저작자표시

+ Recent posts

티스토리툴바