본문 바로가기

카테고리 없음

기본 소팅 알고리즘 5가지


#include<iostream>
#include<stdlib.h>
#include<fstream>
#include<time.h>
using namespace std;
unsigned long cnt;
unsigned long cnt_big;
void selection(int* testcase, int cntcase);
void insertion(int* testcase, int cntcase);
void bubble(int* testcase, int cntcase);
void quick(int* testcase, int low, int high);
void quick_notrecursion(int* testcase, int low, int high);
void merge(int* testcase, int cntcase);
int comp_int(const void* a, const void *b){
 return (*(int*)a - *(int*)b);
}
void main(){
 ifstream fin;
 ofstream fout;
 fin.open("sorted_input.txt");
 //fin.open("input.txt");
 fout.open("output.txt");
 int *testcase;
 int i;
 time_t pre_time, post_time;
 for(int cntcase = 100000; cntcase < 1000001; cntcase += 100000) {
  cout << " Test Case :" << cntcase << endl;
  fout << " Test Case :" << cntcase << endl;
  testcase = (int *)malloc(sizeof(int) * cntcase);

  
  cout << "Selection Sort " << endl;
  fout << "Selection Sort " << endl;
  cnt = 0;
  cnt_big = 0;
  for(i = 0; i < cntcase; i++)
   fin >> testcase[i];
  time(&pre_time);
  selection(testcase,cntcase);
  time(&post_time);
  cout << " 소요시간(단위:초) : " << difftime(post_time, pre_time) << endl;
  cout << " 비교횟수 : " << cnt_big << " " << cnt << endl;
  fout << " 소요시간(단위:초) : " << difftime(post_time, pre_time) << endl;
  fout << " 비교횟수 : " << cnt_big << " " << cnt << endl;
  ////////////////////////////////////////////////
  cout << "Insertion Sort "<< endl;
  fout << "Insertion Sort "<< endl;
  cnt = 0;
  cnt_big = 0;
  for(i = 0; i < cntcase; i++)
   fin >> testcase[i];
  time(&pre_time);
  insertion(testcase,cntcase-1);
  time(&post_time);
  cout << " 소요시간(단위:초) : " << difftime(post_time, pre_time) << endl;
  cout << " 비교횟수 : " << cnt_big << " " << cnt << endl;
  fout << " 소요시간(단위:초) : " << difftime(post_time, pre_time) << endl;
  fout << " 비교횟수 : " << cnt_big << " " << cnt << endl;
  ////////////////////////////////////////////////
  cout << "Bubble Sort "<< endl;
  fout << "Bubble Sort "<< endl;
  cnt = 0;
  cnt_big = 0;
  for(i = 0; i < cntcase; i++)
   fin >> testcase[i];
  time(&pre_time);
  bubble(testcase,cntcase);
  time(&post_time);
  cout << " 소요시간(단위:초) : " << difftime(post_time, pre_time) << endl;
  cout << " 비교횟수 : " << cnt_big << " " << cnt << endl;
  fout << " 소요시간(단위:초) : " << difftime(post_time, pre_time) << endl;
  fout << " 비교횟수 : " << cnt_big << " " << cnt << endl;
  /////////////////////////////////////////////////
  cout << "Quick Sort " <<endl;
  fout << "Quick Sort " <<endl;
  cnt = 0;
  cnt_big = 0;
  for(i = 0; i < cntcase; i++)
   fin >> testcase[i];
  time(&pre_time);
  quick(testcase,0,cntcase-1);
  time(&post_time);
  cout << " 소요시간(단위:초) : " << difftime(post_time, pre_time) << endl;
  cout << " 비교횟수 : " << cnt_big << " " << cnt << endl;
  fout << " 소요시간(단위:초) : " << difftime(post_time, pre_time) << endl;
  fout << " 비교횟수 : " << cnt_big << " " << cnt << endl;
  ////////////////////////////////////////////////
  cout << "Merge Sort " <<endl;
  fout << "Merge Sort " <<endl;
  cnt = 0;
  cnt_big = 0;
  time(&pre_time);
  merge(testcase,cntcase-1);
  time(&post_time);
  cout << " 소요시간(단위:초) : " << difftime(post_time, pre_time) << endl;
  cout << " 비교횟수 : " << cnt_big << " " << cnt << endl;
  fout << " 소요시간(단위:초) : " << difftime(post_time, pre_time) << endl;
  fout << " 비교횟수 : " << cnt_big << " " << cnt << endl;
  ////////////////////////////////////////////////
  cout << "Quick Sort_notrecursion " <<endl;
  fout << "Quick Sort_notrecursion " <<endl;
  cnt = 0;
  cnt_big = 0;
  for(i = 0; i < cntcase; i++)
   fin >> testcase[i];
  time(&pre_time);
  quick_notrecursion(testcase,0,cntcase-1);
  time(&post_time);
  cout << " 소요시간(단위:초) : " << difftime(post_time, pre_time) << endl;
  cout << " 비교횟수 : " << cnt_big << " " << cnt << endl;
  fout << " 소요시간(단위:초) : " << difftime(post_time, pre_time) << endl;
  fout << " 비교횟수 : " << cnt_big << " " << cnt << endl;
  ////////////////////////////////////////////////////////
  cout << "Gnu qsort " <<endl;
  fout << "Gnu qsort " <<endl;
  cnt = 0;
  cnt_big = 0;
  for(i = 0; i < cntcase; i++)
   fin >> testcase[i];
  time(&pre_time);
  qsort(testcase, cntcase, sizeof(int), comp_int);
  time(&post_time);
  cout << " 소요시간(단위:초) : " << difftime(post_time, pre_time) << endl;
  cout << " 비교횟수 : " << cnt_big << " " << cnt << endl;
  fout << " 소요시간(단위:초) : " << difftime(post_time, pre_time) << endl;
  fout << " 비교횟수 : " << cnt_big << " " << cnt << endl;
  /////////////////////////////////////////
  
  free(testcase);
 }
 fin.close();
 fout.close();  
}
void selection(int* testcase, int cntcase){
 int i, j, min;
 for(i = 0; i < cntcase-1; i++){
  min = i;
  for(j = i+1; j< cntcase; j++){
   if(testcase[j] < testcase[min])
    min = j;
   cnt++;
   if(cnt > 100000000) {
    cnt = 0;
    cnt_big++;
   }
  }
  j = testcase[min];
  testcase[min] = testcase[i];
  testcase[i] = j;
 }
}
void insertion(int* testcase, int cntcase){
 int i,j,v;
 for(i = 1; i < cntcase; i++){
  v = testcase[i];
  j = i;
  while(testcase[j-1] > v){
   testcase[j] = testcase[j-1];
   j--;
   cnt++;
   if(cnt > 100000000) {
    cnt = 0;
    cnt_big++;
   }
  }
  testcase[j] = v;
 }
}
void bubble(int* testcase, int cntcase){
 int i,j,tmp;
 for(i = 0; i < cntcase-1; i++)
  for(j = i+1; j< cntcase; j++){
   if(testcase[i] > testcase[j]){
    tmp = testcase[i];
    testcase[i] = testcase[j];
    testcase[j] = tmp;
   }
   cnt++;
   if(cnt > 100000000) {
    cnt = 0;
    cnt_big++;
   }
  }
}
void quick(int* testcase, int low, int high){
 int i, j, tmp;
 int pivotitem;
 if(high > low){
  pivotitem = testcase[low];
  j = low;
  for(i = low+1; i<= high; i++)
   if(testcase[i] < pivotitem)   {
    j++;
    tmp = testcase[i];
    testcase[i] = testcase[j];
    testcase[j] = tmp;
    cnt++;
    if(cnt > 100000000) {
     cnt = 0;
     cnt_big++;
    }
   }
  tmp = testcase[low];
  testcase[low] = testcase[j];
  testcase[j] = tmp;
  quick(testcase, low, j-1);
  quick(testcase, j+1, high);
 }
}
void merge(int* testcase, int cntcase){
 int h = cntcase / 2;
 int m = cntcase - h;
 int i=0,j=0,k=0;
 int *U = (int *)malloc(sizeof(int)*h);
 int *V = (int *)malloc(sizeof(int)*m);
 if(cntcase > 1){
  memcpy(U, testcase, sizeof(int)*h);
  memcpy(V, testcase+h, sizeof(int)*m);
  merge(U, h);
  merge(V, m);
  while(i <= h && j <=m){
   if(U[i] <= V[j])
    testcase[k] = U[i++];
   else
    testcase[k] = V[j++];
   k++;
   cnt++;
   if(cnt > 100000000) {
    cnt -= 100000000;
    cnt_big++;
   }
  }
  if(i > h) memcpy(testcase+k, V+j, sizeof(int)*(m-j));
  else memcpy(testcase+k, U+i, sizeof(int)*(h-i));   
 }
}
struct q{
 int *testcase;
 int low;
 int high;
 q* next;
 
 q(int *a, int b, int c){
  testcase = a;
  low = b;
  high = c;
  next = NULL;
 }
};
void quick_notrecursion(int* testcase, int low, int high){
 q *ptr;
 q *top;
 ptr = new q(testcase, low, high);
 ptr->next = new q(testcase, low, high);
 top = ptr->next;
 int i, j, tmp;
 int pivotitem;
 while(ptr->next != NULL){
  ptr = ptr->next;
  low = ptr->low;
  high = ptr->high;
  testcase = ptr->testcase;
  if(high > low){
   pivotitem = testcase[low];
   j = low;
   for(i = low+1; i<= high; i++)
    if(testcase[i] < pivotitem){
     j++;
     tmp = testcase[i];
     testcase[i] = testcase[j];
     testcase[j] = tmp;
    }
    tmp = testcase[low];
    testcase[low] = testcase[j];
    testcase[j] = tmp;
    top->next = new q(testcase, low, j-1);
    top->next->next = new q(testcase, j+1, high);
    top = top->next->next;
  }
 }
}