#include<iostream.h>   
#include<windows.h>
#include<stdlib.h>
#include<stdio.h>   
#include<time.h>



//選擇排序
class selectionsort
{
	int *array;
	int n;
	int compare;
public:
   selectionsort()
   {
       array=NULL;
	   n=0;
	   compare=0;
   }

void selecsort(int *sarray,int n)     //sarray為存儲數據的數組,n為數組元素個數
{
	int k,temp;        //k用來存儲,臨時最小數據的位置
	for(int i=0;i<n-1;i++)     
	{
		k=i;        
		for(int j=i+1;j<n;j++)    //從第i個數開始選擇最小數位置,存于k中
		{
			compare++;
			if(sarray[j]<sarray[k])
				k=j;
		}
		if(k!=i)       //若最小數,不為sarray[i],則sarray[i]與sarray[k]進行交換
		{
			temp=sarray[i];
			sarray[i]=sarray[k];
			sarray[k]=temp;
		}
	}
}


void Insert(int* sarray,int lenght)
   {
        n=lenght;
    	array=new int[n];
	   for(int i=0;i<n;i++)
	   {
		array[i]=sarray[i];
	   }
   }



   void print()
   {

         //cout<<compare<<endl;
         DWORD   dwStart   =   clock();
         selecsort(array,n);
		 DWORD   dwEnd   =   clock(); 
		 DWORD   dwTimeTaken   =   dwEnd   -   dwStart;
		// cout<<"所用時間為："<<dwTimeTaken<<endl;
	for(int i=0;i<n;i++)
	{
		cout<<array[i]<<'\t';
		if(i%8==7)   cout<<endl;
	}
	cout<<endl; 
	  cout<<"所用時間為："<<dwTimeTaken<<endl;
  cout<<endl; 
   }
};




//插入排序法
class insertsort{

	int* iarray;
	int ilenght;
	int compare;
public:
	insertsort()
	{
		iarray=NULL;
		ilenght=0;
		compare=0;
	}
	void insertion(int* array, int lenght)
	{
		compare++;
		for(int i=1;i<lenght;i++)
		{
			int x=array[i];
			int j=i-1;
			while(j>=0&&array[j]>x)
			{
				compare++;
				array[j+1]=array[j];
				j=j-1;
			}
			array[j+1]=x;
		}
	}

	void Insert(int* array,int lenght)
	{   
		ilenght=lenght;
    	iarray=new int[ilenght];
	   for(int i=0;i<ilenght;i++)
	   {
		iarray[i]=array[i];
	   }
	}

	void print()
	{
		 //cout<<compare;
		 DWORD   dwStart   =   clock();
         insertion(iarray,ilenght);
		 DWORD   dwEnd   =   clock(); 
		 DWORD   dwTimeTaken   =   dwEnd   -   dwStart;
		 //cout<<"所用時間為："<<dwTimeTaken<<endl;
	for(int i=0;i<ilenght;i++)
	{
		cout<<iarray[i]<<'\t';
		if(i%8==7)   cout<<endl;
	}
	cout<<endl; 
	  cout<<"所用時間為："<<dwTimeTaken<<endl;
  cout<<endl; 
   
	}
};



//自底向上排序法
  class   bottomupsort{   
  int   maxsize;   
  int   last;   
  int   slist[10000]; 
  int compare;
  public:   
  bottomupsort()
  {
	  last=0;maxsize=10000;
	  compare=0;
  }   

  int   Length()  const
  {
	  return   last+1;
  }//計算表長度   

  void   Mergesort()
  {
	  int   len=1;   
  int   b[10000];   
  while(len<last){  
	  compare++;
      MergePass(b,len);   
      len=2*len;     
      for(int   i=0;i<last;i++)   slist[i]=b[i];     
  }   
  }

  void   MergePass(int   *b,int   len)
  {
	  int   i,j;   
  i=0;   
  while(i+2*len<last){
	  compare++;
      Merge(b,i,i+len-1,i+2*len-1);     
      i=   i+2*len;             
  }   
  if(i+len<last)   Merge(b,i,i+len-1,last-1);     
  else   for(j=i;j<last;j++)     b[j]=slist[j];
  }

  void   Merge(int*b,int   low,int   mid,int   high)
  {
	  int   i,j,k;   
  i=low;   
  j=mid+1;   
  k=low;   
  while((i<=mid)&&(j<=high)){   
      if(slist[i]<=slist[j])  
	  {
		  b[k++]=slist[i++];
		  compare++;
	  }   
      else
	  {
		  b[k++]=slist[j++];
		  compare++;
	  }
  }   
  while(i<=mid)   b[k++]=slist[i++];  
  while(j<=high)   b[k++]=slist[j++];
  }

  bool   Insert(int   &   elem,int   i)
  {
	  if   (i<0||i>last+1||last==maxsize-1)   return   false;   
  else{   
      for   (int   j=last;j>i;j--)   slist[j]=slist[j-1];   
      slist[i]=elem;   
      last++;   
      return   true;   
  }   
  }

  void   print()
  {
	  
        // cout<<compare;
		 DWORD   dwStart   =   clock();
         Mergesort();
		 DWORD   dwEnd   =   clock();
		 DWORD   dwTimeTaken   =   dwEnd   -   dwStart;
		 //cout<<"所用時間為："<<dwTimeTaken<<endl;
	  int   i;   
      for(i=0;i<last;i++){   
      cout<<slist[i]<<'\t';   
      if(i%8==7)   cout<<endl;   
  }   
	  cout<<endl; 
	  cout<<"所用時間為："<<dwTimeTaken<<endl;
  cout<<endl; 
  }
  };   


//快速排序法
  class quicklist{

	  int* qarray;
	  int qlenght;
	  int compare;
  public:

   quicklist()
   {
	   qarray=NULL;
	   qlenght=0;
	   compare=0;
   }

  void QuickSort(int *pData, int left, int right)
{
     int i, j;
	 int middle,iTemp;
	 i=left;
	 j=right;

	 middle=pData[(left+right)/2];
	 do
	 {
		 while((pData[i]<middle)&&(i<right)) 
		 {
			 compare+=2;
			 i++;
		 }
		 while((pData[j]>middle)&&(j>left))
		 {
			 compare+=2;
			 j--;
		 }
		 if(i<=j)
		 {
			 iTemp=pData[i];
			 pData[i]=pData[j];
			 pData[j]=iTemp;
			 i++;
			 j--;
		 }
	 }while(i<=j);

	 if(left<j) QuickSort(pData,left,j);
	 if(right>i) QuickSort(pData,i,right);
}

void Insert(int * array,int lenght)
{
	qlenght=lenght;
	qarray=new int[qlenght];
	for(int i=0;i<qlenght;i++)
	{
		qarray[i]=array[i];
	}
}

void print()
{	
	     //cout<<compare;
	     DWORD   dwStart   =   clock();
         QuickSort(qarray,0,qlenght-1);
		 DWORD   dwEnd   =   clock(); 
		 DWORD   dwTimeTaken   =   dwEnd   -   dwStart;
		 //cout<<"所用時間為："<<dwTimeTaken<<endl;
	for(int i=0;i<qlenght;i++)
	{
		cout<<qarray[i]<<'\t';
		if(i%8==7)   cout<<endl;
	}

	cout<<endl; 
	cout<<"所用時間為："<<dwTimeTaken<<endl;
	cout<<endl; 
}
};



  void   main(){   
	  int lenght=0;
	  int array[1000];
	  int t=0;

	  cout<<"排序算法平均時間的比較"<<endl;
	  int select;
	  cout<<"請選擇輸入數據類型：1為用隨機產生數據，2為手動輸入數據"<<endl;
	  cin>>select;
	  switch(select)
	  {
	  case 1:
		  lenght=10000;
		  array[10000];
		  srand(time(NULL));
		  for(t=0;t<lenght;t++)
		  {
	          array[t]=rand();
		  }
		  break;
	  case 2:
		  cout<<"請輸入數據量"<<endl;
		  cin>>lenght;
		  cout<<"請輸入要比較的"<<lenght<<"個數:"<<endl;
		  for(t=0;t<lenght;t++)
		  {
			  cin>>array[t];
		  }
		  break;
	  default:
		  lenght=10000;
		  array[10000];
		  srand(time(NULL));
		  for(t=0;t<lenght;t++)
		  {
	          array[t]=rand();
		  }
		  break;
	  }


      selectionsort s;
	  insertsort in;
      bottomupsort   bottomup;
	  quicklist ql;
	  int i=0;
	  bool contimue=true;
	  while(contimue)
	  {
		  cout<<"請選擇排序算法：1.選擇排序法,2.插入排序法,3.自底向上排序法,4.快速排序法"<<endl;
		  cout<<"輸入其它數字則自動結束程序"<<endl;
		  int chioce=0;
		  cin>>chioce;
		  switch(chioce)
		  {
		  case 1:
			  
			  s.Insert(array,lenght);
			  s.print();
			  break;
		  case 2:
              
              in.Insert(array,lenght);
              in.print();
			  break;
		  case 3:  
              for(i=0;i<lenght;i++) bottomup.Insert(array[i],i);
			  bottomup.print();   
			  break;
		  case 4:
			  ql.Insert(array,lenght);
			  ql.print();
			  break;
		  default:
			  contimue=false;
			  break;
		  }
	  }
  }