aa.cpp

#define _CRT_SECURE_NO_WARNINGS

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

//student 구조체 정의
typedef struct student {
   char name[100]; //이름
   int student_number; //학번
   int score; //점수
}student;

typedef struct _time{
   double t[7];
   char name[7][80];
}Time;

Time init_Time(){
   Time this ={
      { 0, },
      {
         "Selection sort: ",
         "Insertion sort: ",
         "Bubble sort: ",
         "Shell sort: ",
         "Merge sort: ",
         "Quick sort: ",
         "Radix sort: "
      }
   };
   return this;
}

//bubble_Sort 정의
void bubble_Sort(student *arr, student *temporary) {
   student s_tmp[100];
   student wh_temp;
   int i, j;
   for (i = 0; i < 100; i++) {
      s_tmp[i] = arr[i];//구조체에 받기
   }

   //버블정렬 진행
   for (i = 0; i < 100; i++) {
      for (j = 0; j < 99 - i; j++) {
         if (s_tmp[j].score < s_tmp[j + 1].score) {
            wh_temp = s_tmp[j];
            s_tmp[j] = s_tmp[j + 1];
            s_tmp[j + 1] = wh_temp;
         }
      }
   }
   for (i = 0; i < 100; i++)
      temporary[i] = s_tmp[i];
}

//selection_Sort 정의 
void selection_Sort(student *arr, student *temporary) {
   int index, temp, i, j;
   student s_tmp[100];
   student wh_temp;

   for (i = 0; i < 100; i++) {
      s_tmp[i] = arr[i]; //구조체에 받기
   }
   //선택정렬 진행
   for (i = 0; i < 100; i++) {
      int max = s_tmp[i].score;
      int index = i;
      for (j = i; j < 100; j++) {
         index = max < s_tmp[j].score ? j : index;
         max = s_tmp[index].score;
      }
      wh_temp = s_tmp[index];
      s_tmp[index] = s_tmp[i];
      s_tmp[i] = wh_temp;
   }

   for (i = 0; i < 100; i++)
      temporary[i] = s_tmp[i];

}

//quick_Sort 정의
void quick_Sort(student *arr, int first, int last) {
   int pivot = arr[first].score;
   int i, j = first, k;
   for (i = first + 1; i < last; i++)
      if (pivot < arr[i].score) {
         student tmp = arr[i];
         for (k = i - 1; k >= j; k--)
            arr[k + 1] = arr[k];
         arr[j++] = tmp;
      }
   if (first >= last)
      return;
   quick_Sort(arr, first, j);
   quick_Sort(arr, j + 1, last);
}

//quic_Sort 정의
void quic_Sort(student *arr, student *temporary) {
   student s_tmp[100];
   int i;
   for (i = 0; i < 100; i++) {
      s_tmp[i] = arr[i]; //구조체에 받기
   }
   quick_Sort(s_tmp, 0, 100);

   for (i = 0; i < 100; i++)
      temporary[i] = s_tmp[i];
}

//merge 정의
void merge(student *arr, int first, int last) {
   student* sorted;
   sorted = (student*)malloc((last + 1) * sizeof(student));

   int mid = (first + last) / 2;
   int s1 = first;
   int s2 = mid + 1;

   //merge
   for (int i = first; i <= last; i++) {
      if (arr[s1].score <= arr[s2].score && s1 <= mid && s2 <= last)
         sorted[i] = arr[s2++];
      else if (arr[s1].score > arr[s2].score && s1 <= mid && s2 <= last)
         sorted[i] = arr[s1++];
      else if (s1 > mid)
         sorted[i] = arr[s2++];
      else if (s2 > last)
         sorted[i] = arr[s1++];
   }
   for (int i = first; i <= last; ++i)
      arr[i] = sorted[i];

   free(sorted);
}

//merge_sort2 정의
void merge_sort2(student *arr, int first, int last) {
   if (first < last) {
      int  mid = (first + last) / 2;
      merge_sort2(arr, first, mid);
      merge_sort2(arr, mid + 1, last);
      merge(arr, first, last);
   }
   else
      return;
}

//merge_sort 정의
void merge_Sort(student *arr, student *temporary) {
   student s_tmp[100];
   int i;
   for (i = 0; i < 100; i++) {
      s_tmp[i] = arr[i]; //구조체에 받기
   }

   merge_sort2(s_tmp, 0, 99);

   for (i = 0; i < 100; i++)
      temporary[i] = s_tmp[i];
}


//insertion_Sort 정의
void insertion_Sort(student *arr, student *temporary) {
   student s_tmp[100];
   student wh_temp;
   int i, j;
   for (i = 0; i < 100; i++) {
      s_tmp[i] = arr[i]; //구조체에 받기
   }
   for (i = 1; i < 100; i++) {
      wh_temp = s_tmp[i];
      j = i - 1;
      while ((j >= 0) && (wh_temp.score > s_tmp[j].score)) {
         s_tmp[j + 1] = s_tmp[j];
         j--;
      }
      s_tmp[j + 1] = wh_temp;
   }
   for (i = 0; i < 100; i++)
      temporary[i] = s_tmp[i];
}

//r_insertion_Sort 정의
void r_insertion_Sort(student *arr, int first, int space) {
   for (int i = first + space; i < 100; i += space) {
      student key = arr[i];
      int j;
      for (j = i - space; j >= first && key.score > arr[j].score; j -= space)
         arr[j + space] = arr[j];
      arr[j + space] = key;
   }
}

//radix_Sort 정의
void radix_Sort(student *arr, student *temporary) {
   int i, j, l, sum = 0;;
   student s_tmp[100];
   for (i = 0; i < 100; i++) {
      s_tmp[i] = arr[i];
   }
   //기수정렬 진행
   for (i = 1; i <= 100; i *= 10) {
      student queueueue[10][100] = { { 0, }, };
      int k[10] = { 0, };
      for (j = 0; j < 100; j++) {
         int temp = (s_tmp[j].score / i) % 10;
         queueueue[temp][k[temp]] = s_tmp[j];
         k[temp]++;
      }
      for (j = 9; j >= 0; j--) {
         for (l = 0; l < k[j]; l++) {
            s_tmp[l + sum] = queueueue[j][l];
         }
         sum += l;
      }
      sum = 0;
   }

   
   for (i = 0; i < 100; i++)
      temporary[i] = s_tmp[i];
}

//shell_Sort 정의
void shell_Sort(student *arr, student *temporary) {
   student s_tmp[100];
   int i;
   int space;
   for (i = 0; i < 100; i++) {
      s_tmp[i] = arr[i]; //구조체에 받기
   }

   //shell_Sort
   for (int space = 50; space > 0; space /= 2) {
      if (space % 2 == 0) {
         space++;
      }
      for (i = 0; i < space; i++) {
         r_insertion_Sort(s_tmp, i, space);
      }
   }
   
   for (i = 0; i < 100; i++)
      temporary[i] = s_tmp[i];
}

//main함수
int main(void) {
   student arr_student[100];
   float total_time[7] = { 0.0f, };
   float average_time[7] = { 0.0f, };
   clock_t initial_time;
   student temporary[100];
   Time timer = init_Time();
   clock_t temp;

   int i = 0;
   int j, k;
   int p;

   srand(time(NULL));
   printf("학번\t\t 점수   \t이름 \n\n");
   FILE *fp;
   fp = fopen("C:\\Users\\hjcha\\Desktop\\Student_info.txt", "r");
   if (fp == NULL) {
      printf("file open error!\n");
      return 1;
   }
   while (!feof(fp)) {
      fscanf(fp, "%d\t", &arr_student[i].student_number);
      fgets(arr_student[i].name, sizeof(arr_student[i].name), fp);
      arr_student[i].score = rand() % 101;
      i++;
   }//file 읽어오기

   for (i = 0; i < 100; i++) {
   printf("학번:%d  점수:%4d  이름: %s\n", arr_student[i].student_number, arr_student[i].score, arr_student[i].name);
   }//학생들의 학번, 이름, 점수 출력

   //100번 정렬 후 100번째 정렬의 결과 출력
   for (j = 0; j < 100; j++) {
      initial_time = clock();
      selection_Sort(arr_student, temporary);
      total_time[0] = total_time[0] + clock() - initial_time;

      if (j == 99) {
         printf("---------After Selection Sort-------------\n");
         for (p = 0; p < 100; p++) {
            printf("%4d ", temporary[p].score);
         }
      }

      initial_time = clock();
      insertion_Sort(arr_student, temporary);
      total_time[1] = total_time[1] + clock() - initial_time;

      if (j == 99) {
         printf("\n\n---------After Insertion Sort-------------\n");
         for (p = 0; p < 100; p++) {
            printf("%4d ", temporary[p].score);
         }
      }

      initial_time = clock();
      bubble_Sort(arr_student, temporary);
      total_time[2] = total_time[2] + clock() - initial_time;
      if (j == 99) {
         printf("\n\n---------After Bubble Sort-------------\n");
         for (p = 0; p < 100; p++) {
            printf("%4d ", temporary[p].score);
         }
      }

      initial_time = clock();
      shell_Sort(arr_student, temporary);
      total_time[3] = total_time[3] + clock() - initial_time;
      if (j == 99) {
         printf("\n\n---------After Shell Sort-------------\n");
         for (p = 0; p < 100; p++) {
            printf("%4d ", temporary[p].score);
         }
      }

      initial_time = clock();
      merge_Sort(arr_student, temporary);
      total_time[4] = total_time[4] + clock() - initial_time;
      if (j == 99) {
         printf("\n\n---------After Merge Sort-------------\n");
         for (p = 0; p < 100; p++) {
            printf("%4d ", temporary[p].score);
         }
      }

      initial_time = clock();
      quic_Sort(arr_student, temporary);
      total_time[5] = total_time[5] + clock() - initial_time;
      if (j == 99) {
         printf("\n\n---------After Quick Sort-------------\n");
         for (p = 0; p < 100; p++) {
            printf("%4d ", temporary[p].score);
         }
      }

      initial_time = clock();
      radix_Sort(arr_student, temporary);
      total_time[6] = total_time[6] + clock() - initial_time;
      if (j == 99) {
         printf("\n\n---------After Radix Sort-------------\n");
         for (p = 0; p < 100; p++) {
            printf("%4d ", temporary[p].score);
         }
      }
      fflush(fp);
      fclose(fp);
   }

   //정렬 당 평균 소요시간 구하기
   for (i = 0; i < 100; i++) {
      temp = clock();

      selection_Sort(arr_student, temporary);
      timer.t[0] += (((clock() - (double)temp) / CLOCKS_PER_SEC) - timer.t[0]) / (i + 1);
      temp = clock();
      insertion_Sort(arr_student, temporary);
      timer.t[1] += (((clock() - (double)temp) / CLOCKS_PER_SEC) - timer.t[1]) / (i + 1);
      temp = clock();
      bubble_Sort(arr_student, temporary);
      timer.t[2] += (((clock() - (double)temp) / CLOCKS_PER_SEC) - timer.t[2]) / (i + 1);
      temp = clock();
      shell_Sort(arr_student, temporary);
      timer.t[3] += (((clock() - (double)temp) / CLOCKS_PER_SEC) - timer.t[3]) / (i + 1);
      temp = clock();
      merge_Sort(arr_student, temporary);
      timer.t[4] += (((clock() - (double)temp) / CLOCKS_PER_SEC) - timer.t[4]) / (i + 1);
      temp = clock();
      quic_Sort(arr_student, temporary);
      timer.t[5] += (((clock() - (double)temp) / CLOCKS_PER_SEC) - timer.t[5]) / (i + 1);
      temp = clock();
      radix_Sort(arr_student, temporary);
      timer.t[6] += (((clock() - (double)temp) / CLOCKS_PER_SEC) - timer.t[6]) / (i + 1);
   }

   printf("\n\n-----Average Time Spent in Each Sort----- \n");
   for (i = 0; i < 7; i++){
      printf("%16s", timer.name[i]);
      printf("%.8lfsec\n", timer.t[i]);
   }//각 정렬의 평균 소요시간 출력

   int     shortest = 0;
   double  t = 1.0;
   for (i = 0; i < 7; i++){
      shortest = timer.t[i] < t ? i : shortest;
      t = timer.t[shortest];
   }//가장 짧은 시간이 걸리는 정렬 출력
   printf("\n%16s\n%16s %.8lfsec\n\n",
      "<Sort Taking LEAST amount of Time> ",
      timer.name[shortest], timer.t[shortest]);
   
   return 0;
}