#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <time.h>
#define N 100000
#define FILE_NAME "dataDemo"

unsigned short x[N];

//讀取檔案 dataDemo.txt 至陣列 x 
void ReadData(){
	int i;
	FILE *fp = fopen(FILE_NAME ".txt", "r");
	for(i=0;i<N;i++)
		fscanf(fp,"%u",x+i);
	fclose(fp);
}

//輸出陣列 x 至檔案 data1.txt
void SaveData(){
	int i;
	FILE *fp = fopen(FILE_NAME "1.txt", "w");	
	for(i=0;i<N;i++)
		fprintf(fp,"%d ",x[i]);
	fclose(fp);
}

//檢查輸出檔案是否由小至大排列 
void CheckData(char *s){
	int i,a,b;
	FILE *fp = fopen(FILE_NAME "1.txt", "r");
	std::cout << s;
	fscanf(fp,"%d",&a);
	for(i=1;i<N;i++){
		fscanf(fp,"%d",&b);
		if(a>b) std::cout << "Error data : (" << i << ") " << b << std::endl;
		a=b;
	}
	std::cout << "Ok\n\n";
	fclose(fp);
}

//交換 
void swap(unsigned short &a, unsigned short &b){
unsigned short c;
c=a;a=b;b=c;	
}

//汽泡排序 
void BubbleSort(){
	int i,j,ki=N-1,kj;
	for(i=0;i<ki;i++){
		kj=N-i-1;
		for(j=0;j<kj;j++)
			if(x[j]>x[j+1]) swap(x[j],x[j+1]);
	}
}

//改良式汽泡排序 
void AdvBubbleSort(){
	int i,j,ki=N-1,d;
	for(i=0;i<ki;i++){
		d=i;
		for(j=i+1;j<N;j++)
			if(x[j]<x[d]) d=j;
		if(d!=i) swap(x[i],x[d]);
	}
}

//薛爾排序
void SellSort(){
	int gap=N/2, i,n,f,a,b;
	while(gap>0){
    	for(i=0;i<gap;i++){
			do{
				a=i;
				b=a+gap;
				f=0;
	    		while(b<N){
    				if(x[a]>x[b]){
    					f=1;
    					swap(x[a],x[b]);
					}
					a=b;
					b=a+gap;
				}
			}while(f);
    	}
		gap/=2;
	}
}

//快速排序 範圍 m ~ n 
void QuickSort(int m, int n){
	int L,R,k;
	if(m<n){
		L=m;
		R=n+1;
		k=x[m];
		do{
			do{
				L++;
			}while(x[L]<k);
			do{
				R--;
			}while(x[R]>k);
			if(L<R){
				swap(x[L],x[R]);
			}
		}while(L<R);
		swap(x[m],x[R]);
		QuickSort(m,R-1);
		QuickSort(R+1,n);
	}
}

PrnTime(const char *s,struct timeval t1,struct timeval t2){
	int a,b;
	a=t2.tv_sec-t1.tv_sec;
	b=t2.tv_usec-t1.tv_usec;
	if(b<0){
		a--;
		b+=1000000;
	}
	std::cout << s << a << "." << b << std::endl;
}

int main(int argc, char** argv) {
	int a,i;
	struct timeval t1,t2;
	
	//***** 汽泡排序 *****
	ReadData();
    gettimeofday(&t1,NULL);
	BubbleSort();	
	gettimeofday(&t2,NULL);
	PrnTime("Bubble Sort run time : ",t1,t2);
	SaveData();
	CheckData("Bubble Sort check:");
	
	//***** 改良式汽泡排序 *****
	ReadData();
    gettimeofday(&t1,NULL);
	AdvBubbleSort();	
	gettimeofday(&t2,NULL);
	PrnTime("Advance Bubble Sort run time : ",t1,t2);
	SaveData();
	CheckData("Advance Bubble Sort check:");
	
	//***** Shell 排序 *****
	ReadData();
    gettimeofday(&t1,NULL);
	SellSort();	
	gettimeofday(&t2,NULL);
	PrnTime("Shell Sort run time : ",t1,t2);
	SaveData();
	CheckData("Shell Sort check:");
	
	//***** Quick 排序 *****
	ReadData();
    gettimeofday(&t1,NULL);
	QuickSort(0,N-1);	
	gettimeofday(&t2,NULL);
	PrnTime("Quick Sort run time : ",t1,t2);
	SaveData();
	CheckData("Quick Sort check:");
	return 0;
}