자료구조 ( 실습1 )

 

1. 선택 정렬 : Selection sort

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <math.h> #define MAX_SIZE 500001 #define SWAP(x,y,t)((t)=(x), (x)=(y), (y)=(t)) void sort(int[], int); void main(void) {     int i, n, list[MAX_SIZE];     printf("Enter the number of numbers to generate: ");     scanf("%d", &n);     if (n<1 || n>MAX_SIZE) {         fprintf(stderr, "Improper value of n\n");         exit(1);     }     // 난수 초기화     srand(time(NULL));     for (i = 0; i < n; i++) {         list[i] = rand() % 1000;         //printf("%d ", list[i]);     }     // 시간 측정 시작     sort(list, n);     // 시간 측정 종료     printf("\n Sorted array:\n");     for (i = 0; i < n; i++)         printf("%d ", list[i]);     printf("\n");     } void sort(int list[], int n) {     int i, j, min, temp;     for (i = 0; i < n - 1; i++) {         min = i;         for (j = i + 1; j < n; j++)             if (list[j] < list[min])                 min = j;         SWAP(list[i], list[min], temp);     } }

           

#include <stdio.h> #include <time.h> void func() {     int result = 0;     for (int i = 0; i < 1000; i++) {         result += i;     } } int main() {     clock_t start, stop;     double duration;          start = clock();     func(); // sort() or search() // 실행 시간 알 수 있다.     stop = clock();          duration = ((double)(stop - start)) / CLK_TCK;     printf("실행시간 : %.8f", duration); }

 

3. 이진 탐색 : Binary search

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #define compare(x, y) (((x) < (y)) ? -1 : ((x)==(y))? 0 : 1) #define MAX_SIZE 7 int binsearch(int list[], int searchnum, int left, int right); void main() {     int list[MAX_SIZE] = { 1, 4, 8, 11, 13, 16, 23 };     printf("%d", binsearch(list, 8, list[0], list[MAX_SIZE - 1])); } int binsearch(int list[], int searchnum, int left, int right) {     int middle;     int count =0;     while (left <= right) {         count++;         middle = (left + right) / 2;         switch (compare(list[middle], searchnum)) {             case -1:                 // searchnum이 list[middle]보다 큰 경우                 left = middle + 1;                 break;             case 0:                 // searchnum이 list[middle]과 같은 경우                 return count;             case 1:                 // searchnum이 list[middle]보다 작은 경우                 right = middle - 1;             }         }     return -1; }

2. 선형 탐색 : Linear search

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #define MAX_SIZE 6 int linearSearch(int list[], int searchNum); void main() {     int searchNum = 5;     int list[MAX_SIZE] = { 6, 8, 3, 5, 2, 1 };     int idx = 0;     idx = linearSearch(list, searchNum);     if (idx==1) printf("%d번째 인덱스에 존재합니다.", idx);     else printf("찾고자 하는 숫자가 존재 하지 않습니다,"); } int linearSearch(int list[], int searchNum) {     for (int i = 0; i < MAX_SIZE; i++)        if (list[i] == searchNum) return i;     return -1; }

2, 3 비교

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <math.h> #define MAX_SIZE 100001 #define compare(x, y) (((x) < (y)) ? -1 : ((x)==(y))? 0 : 1) int linearSearch(int list[], int searchNum); int binsearch(int list[], int searchnum, int left, int right); void main() {    int list[MAX_SIZE];    int list2[MAX_SIZE];    int n = 0;    int result = 0;    int result2 = 0;    int searchNum = 0;    printf("Enter the number of numbers to generator : ");    scanf("%d", &n);    for (int i = 0; i < n; i++) {       list[i] = i + 1;    }    srand(time(NULL));    for (int i = 0; i < n; i++) {       list2[i] = rand() % n;    }    srand(time(NULL));    searchNum = list2[rand() % n];    result = binsearch(list, searchNum, list[0], list[n - 1]);    result2 = linearSearch(list2, searchNum);    printf("이진탐색 : %d를 찾은 횟수 : %d\n", searchNum, result);    printf("선형탐색 : %d를 찾은 횟수 : %d\n", searchNum, result2); } int binsearch(int list[], int searchnum, int left, int right) {    int middle;    int count = 0;    while (left <= right) {       count++;       middle = (left + right) / 2;       switch (compare(list[middle], searchnum)) {       case -1:          // searchnum이 list[middle]보다 큰 경우          left = middle + 1;          break;       case 0:          // searchnum이 list[middle]과 같은 경우          return count;       case 1:          // searchnum이 list[middle]보다 작은 경우          right = middle - 1;       }    }    return -1; } int linearSearch(int list[], int searchNum) {    for (int i = 0; i < MAX_SIZE; i++)       if (list[i] == searchNum) return i;    return -1; }