#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;
}
}
}
