#include<iostream.h>
#include<time.h>
#include<stdlib.h>
int converttime1=0,converttime2,converttime3,converttime4;//定義交換次數

//直接插入排序
int *Insertionsort(int *A,int n)
{
 int j,item,i;
 for(j=2;j<=n;j++)
 {
  item=A[j];
      i=j-1;
  

  while (item<A[i])
  {
   A[i+1]=A[i];
   i--;
  }
  A[i+1]=item;
  converttime2++;
 }
 return A;
}//直接插入排序
//-----------------------------------------------------------------------

//快速排序
int Quickpass(int R[],int  low,int  high)
{
 int down,up; //initialize  flag
 down=low;up=high;R[0]=R[low]; //put benchmark record into R[0]
 while (down<up)
 {
  while((down<up)&&(R[up]>=R[0])) //scan from right to left
   up--;
  if(down<up)
   R[down++]=R[up];
  
  while((down<up)&&(R[down]<=R[0]))//scan from left to right
   down++;
  if(down<up)
   R[up--]=R[down];
  
 }
 R[down]=R[0];
 return down;
}//one time of sortion


int  *Quicksort(int R[],int low,int high)
{
 int mid;
 if (low<high)
 {
  mid=Quickpass(R,low,high);
  Quicksort(R,low,mid-1);
  Quicksort(R,mid+1,high);
  converttime1++;
 }
 return R;

}//快速排序
//-------------------------------------------------------------------------------

//冒泡排序
int *maopao(int data[],int m)
{
int i,j,temp;//data存放要排序的數據。   
                                   
   
  for(j   =   0;j<m-1;j++)//比較number-1次   
  {   
  for(i   =   0;i<m-1;i++)   
  {   
  if(data[i+1]<data[i])//交換順序   
  {   //counttime1++;
  temp   =   data[i+1];   
  data[i+1]   =   data[i];   
  data[i]   =   temp; 
  converttime3++;
  
  }   
  }   
  }
  return data;
}
//冒泡排序
//----------------------------------------------------------------------------------


//直接選擇排序
void selectsort(int s[],int m)
{
	int i,j,k;int t;
	for(i=0;i<m-1;i++)
	{
		k=i;
		for(j=i+1;j<m;j++)
			if(s[j]<s[k])k=j;
			if(k!=i)
			{
				t=s[i];
				s[i]=s[k];
				s[k]=t;
				converttime4++;
			}
	}
}
//直接選擇排序
//------------------------------------------------------------------------------------


//輸出限制函數
void confine(int i)
{
        
        if(i%10==0)
          cout<<endl;
}
//-------------------------------------------------------------------------------------


//主函數
void main()
{

 clock_t start,end;
 float elapsed1; //time of quicksort
 float elapsed2; //time of insertionsort
 float elapsed3;//time of maopaosort
 float elapsed4;//time of selectsort
// float elapsed4;
 const int n=20001;//數據規模
 const int m=20000;//數據規模
 int i;int w;

 cout<<"|------2006-2007數據結構課程設計---------|"<<endl;
 cout<<"|---------四種排序算法的比較-------------|"<<endl;
 cout<<"|-----------數據規模：20000--------------|"<<endl;
 cout<<"|---power by huangjianqun(02210050211)---|"<<endl;
 cout<<"  ---------------------------------------"<<endl;
 cout<<"running……"<<endl;

while(w)
{
 //產生隨機數
  int sj[m];
  for(i=0;i<m;i++)
  sj[i]=rand();


 //INSERTIONSORT//計算直接插入排序的時間
    
 start=clock(); //start time
 

 int A[m];
 for(i=0;i<m;i++)
 A[i]=rand();


    Insertionsort(A,m);

 end=clock(); //finish time

 elapsed2=((float)end-start)/CLOCKS_PER_SEC;



//INSERTIONSORT


//QUICKSORT
 
 
 start=clock();//start time
    int R[n];
    for(i=1;i<=n;i++)
 R[i]=rand();

    Quicksort(R,1,n);

    end=clock(); //time finish

 elapsed1=((float)end-start)/CLOCKS_PER_SEC;
//QUICKSORT

//maopao

 start=clock();//start time
 int data[m];
 for(i=1;i<=m;i++)
	 data[i]=rand();

    maopao(data,m);

	end=clock();
	elapsed3=((float)end-start)/CLOCKS_PER_SEC;

//selectsort
  start=clock();//start time
  int s[m];
  for(i=1;i<=m;i++)
  s[i]=rand();
  selectsort(s,m);
  end=clock();
  elapsed4=((float)end-start)/CLOCKS_PER_SEC;
 cout<<"選擇<7>退出;"<<endl;
 cout<<"選擇<6>比較算法的交換次數"<<endl;
 cout<<"選擇<5>驗證selectsort的正確性"<<endl;
 cout<<"選擇<4>驗證maopao的正確性"<<endl;
 cout<<"選擇<3>驗證insertionsort的正確性"<<endl;
 cout<<"選擇<2>驗證quicksort的正確性"<<endl;
 cout<<"選擇<1>比較算法運算時間"<<endl;
 cout<<"選擇<0>產生20000 個隨機數"<<endl;
 cout<<"請輸入您的選擇：";
 cin>>w;
 switch(w){
  case 7:break;
  case 6: cout<<"insertionsort的交換次數為："<<converttime2<<endl;
	      cout<<"quicksort的交換次數為："<<converttime1<<endl;
		  cout<<"maopaosort的交換次數為："<<converttime3<<endl;
		  cout<<"selectsort的交換次數為:"<<converttime4<<endl;
		  cout<<"通過比較可知，交換所用次數最少的是："<<"快速排序(quicksort)"<<converttime1<<"次"<<endl;
		  break;

  case 5:for(i=0;i<m;i++)
		 {
			 cout<<s[i]<<" ";
	         confine(i);
		 }

	  break;
  case 4:for(i=0;i<m;i++)
		 {
			cout<<data[i]<<" ";
	        confine(i);
		 }
	        
	  
	 break;
  case 3:for(i=0;i<m;i++)
		 {
         cout<<A[i]<<" ";
	     confine(i);
		 }
   break;
  case 2:for(i=1;i<n;i++)
		 {
         cout<<R[i]<<" ";
	     confine(i);
		 }
		 

   break;
  case 1: cout<<"insertionsort的運行時間:"<<elapsed2<<"s"<<endl;
          cout<<"quicksort的運行時間:"<<elapsed1<<"s"<<endl;
		  cout<<"maopaosort的運行時間:"<<elapsed3<<"s"<<endl;
		  cout<<"selectsort的運行時間:"<<elapsed4<<"s"<<endl;
		  cout<<"通過比較可知，排序所用時間最短的算法為快速排序(quicksort):"<<elapsed1<<"s"<<endl;
		 
		 
   break;
  case 0:for(i=0;i<m;i++)
		 {
	     cout<<sj[i]<<" ";
	     confine(i);
		 }


    break;
         

  default: cout<<"錯誤！請輸入正確的功能序號!"<<endl;
 }
 
}
}