#include<iostream>
#include<conio.h>
#include <windows.h>
#define MAXSTACK 2048

using namespace std;

template<class T>
void BubbleSortVer1(T a[], long size)
 {
  long i,j;
  T x;
 
 for(i=0;i<size;i++)
  {           
    for(j=size-1;j >i;j--) 
    {   
      if (a[j-1]>a[j])
     {
      x=a[j-1];
      a[j-1]=a[j]; 
      a[j]=x;
     }
    }
  }
 }
 
template<class T>
void BubbleSortVer2(T a[], long size)
{
  long j, k = size-1;
  long lb=1, ub = size-1;
  T x;

  do
  {
    for(j=ub;j>0;j--)
     {
      if (a[j-1]>a[j])
       {
        x=a[j-1]; 
        a[j-1]=a[j]; 
        a[j]=x;
        k=j;
       }
     }

    lb = k+1;
 
    for(j=1;j<=ub;j++)
     {
      if (a[j-1]>a[j])
       {
        x=a[j-1];
        a[j-1]=a[j]; 
        a[j]=x;
        k=j;
       }
     }

    ub = k-1;
   }
   while (lb<ub);
}

template<class T>
void ChoiceSort(T a[], long size)
{
  long i,j,k; 
  T x;

  for(i=0;i<size;i++)
   {  
    k=i;
    x=a[i];

    for( j=i+1;j<size;j++)
      if (a[j]<x) 
      {
        k=j;
        x=a[j];	      
      }

    a[k]=a[i];
    a[i]=x;  
   }
}

template<class T>
void InsertSortVer1(T a[], long size)
{
  T x;
  long i, j;

  for (i=0;i<size;i++)
   { 
    x=a[i];
		
    for (j=i-1;j>=0&&a[j]>x;j--)
      a[j+1]=a[j]; 

    a[j+1]=x;
  }
}

template<class T>
void SetMin(T& val)
{
    val=static_cast<T>(std::numeric_limits<double>::min());
}

template<class T>
void InsertSortVer2(T a[], long size)
{
  T x;
  long i, j;
  T backup=a[0];			

  SetMin(a[0]);			

  for (i=1;i<size;i++)
   {  	
    x=a[i];
		 
    for (j=i-1;a[j]>x;j--)
	  a[j+1]=a[j];

	a[j+1]=x;
  }

  for (j=1;j<size&&a[j]<backup;j++)
    a[j-1]=a[j];

   
  a[j-1]=backup;
}

int increment(long inc[], long size)
{
  int p1,p2,p3,s;

  p1=p2=p3=1;
  s=-1;
  do
  {
    if (++s % 2)
    {
      inc[s]=8*p1-6*p2+1;
    } 
    else
     {
      inc[s]=9*p1-9*p3+1;
      p2*=2;
      p3*=2;
     }
	p1*=2;
   }
   while(3*inc[s]<size);  

  return s>0?--s:0;
}

template<class T>
void ShellSort(T a[], long size)
{
  long inc, i, j, seq[40];
  int s;

  s=increment(seq, size);
  while (s>=0)
   {
	inc=seq[s--];

    for (i=inc;i<size;i++)
     {
      T temp=a[i];
      for (j=i-inc;(j >= 0)&&(a[j]>temp);j -= inc)
        a[j+inc]=a[j];
       a[j+inc]=temp;
     }
   }
}

template<class T>
void downPyramid(T a[], long k, long n)
{ 
  T new_elem;
  long child;
  new_elem=a[k];

  while(k <= n/2)
  {  	
    child=2*k;
    if( child<n&&a[child]<a[child+1]) 
    child++;
    
    if(new_elem>=a[child]) break; 
    
    a[k]=a[child]; 
    k=child;
  }
  a[k]=new_elem;
}

template<class T>
void PyramidSort(T a[], long size)
{
  long i;
  T temp;

  for(i=size/2-1;i>=0;i--)
   downPyramid(a,i,size-1);
   
  for(i=size-1;i>0;i--)
   { 
    temp=a[i];
    a[i]=a[0];
    a[0]=temp;
    downPyramid(a,0,i-1); 
  }
}

template<class T>
void QuickSortVer1(T* a, long N)
{
  long i=0, j=N; 		
  T temp, p;

  p=a[N>>1];	

  do
  {
    while (a[i]<p)
     i++;
    while (a[j]>p)
     j--;

    if (i<=j)
    {
      temp=a[i];
      a[i]=a[j];
      a[j]=temp;
      i++;
      j--;
    }
  }
   while (i<=j);


  if (j>0) QuickSortVer1(a,j);
  if ( N>i) QuickSortVer1(a+i,N-i);
}

template<class T>
void QuickSortVer2(T a[], long size)
{

  long i, j;   	
  long lb, ub;  	
  long lbstack[MAXSTACK], ubstack[MAXSTACK]; 
  long stackpos = 1;   	
  long ppos;            
  T pivot;             
  T temp; 

  lbstack[1]=0;
  ubstack[1]=size-1;

  do
  {
 
    lb=lbstack[stackpos];
    ub=ubstack[stackpos];
    stackpos--;

    do
    {
      ppos=(lb+ub)>>1;
      i=lb;
      j=ub;
      pivot=a[ppos];

      do
      {
        while (a[i]<pivot) i++;
        while (pivot<a[j]) j--;

        if (i<=j)
         {
          temp=a[i];
          a[i]=a[j]; 
          a[j]=temp;
          i++;
          j--;
         }
       }
      while ( i <= j );

      if (i<ppos)
      {     
          if ( i < ub )
          {   
          stackpos++; 
          lbstack[stackpos]=i;
          ubstack[stackpos]=ub;
          }
          ub = j;      
          
      }
       else 
       {       	 

        if (j>lb)
         { 
          stackpos++;
          lbstack[stackpos]=lb;
          ubstack[stackpos]=j;
         }
        lb = i;
      }

    }
   while (lb<ub);     

   }
    
  while (stackpos!=0);   
}

void Message()
{
    cout<<endl;
    cout<<"Please, choose the method of sorting massive!"<<endl<<endl; 
    
    cout<<"1. BubbleSortVer1 "<<endl;
    cout<<" 2. BubbleSortVer2 "<<endl;
    cout<<"  3. ChoiceSort "<<endl;
    cout<<"   4. InsertSortVer1 "<<endl;
    cout<<"    5. InsertSortVer2 "<<endl;
    cout<<"   6. ShellSort "<<endl;
    cout<<"  7. PyramidSort "<<endl;
    cout<<" 8. QuickSortVer1 "<<endl;
    cout<<"9. QuickSortVer2 "<<endl<<endl;
    
    cout<<"Enter 'ESC' for Exit!"<<endl<<endl;
     }

template <class T>
void Work() {

int ch,size;
T a[size];
               
cout<<"Please, enter the size of massive to sort!"<<endl;   
cin>>size;

 while (ch !=27)
       
  {  
       Message();
       ch = getch();
     
         switch(ch)
         
  {    case 49:
       
      { srand((unsigned int)time(0)); 
             for(int i=0;i<size;i++)
              {
                a[i]=rand()%100; 
              }

               for(int i=0;i<size;i++)
                {
                  cout<<a[i]<<" ";
                }
     
          cout << endl;

                int time=GetTickCount(); 
                BubbleSortVer1<T>(a, size); 
                time=GetTickCount()-time; 

                for(int i=0; i<size;i++)
                 {
                   cout<<a[i]<<" ";
                 }
       
          cout<<endl;

         cout<<"time = "<<time<<endl;
       }
       
	     break;
	     
       case 50:
            
            { srand((unsigned int)time(0)); 
             for(int i=0;i<size;i++)
              {
                a[i]=rand()%100; 
              }

               for(int i=0;i<size;i++)
                {
                  cout<<a[i]<<" ";
                }
     
          cout << endl;

                int time=GetTickCount(); 
                BubbleSortVer2<T>(a, size); 
                time=GetTickCount()-time; 

                for(int i=0; i<size;i++)
                 {
                   cout<<a[i]<<" ";
                 }
       
          cout<<endl;

         cout<<"time = "<<time<<endl;
       }
            
	     break;
	     
       case 51:
            
            { srand((unsigned int)time(0)); 
             for(int i=0;i<size;i++)
              {
                a[i]=rand()%100; 
              }

               for(int i=0;i<size;i++)
                {
                  cout<<a[i]<<" ";
                }
     
          cout << endl;

                int time=GetTickCount(); 
                ChoiceSort<T>(a, size); 
                time=GetTickCount()-time; 

                for(int i=0; i<size;i++)
                 {
                   cout<<a[i]<<" ";
                 }
       
          cout<<endl;

         cout<<"time = "<<time<<endl;
       }
            
	     break;
  
       case 52:
            
            { srand((unsigned int)time(0)); 
             for(int i=0;i<size;i++)
              {
                a[i]=rand()%100; 
              }

               for(int i=0;i<size;i++)
                {
                  cout<<a[i]<<" ";
                }
     
          cout << endl;

                int time=GetTickCount(); 
                InsertSortVer1<T>(a, size); 
                time=GetTickCount()-time; 

                for(int i=0; i<size;i++)
                 {
                   cout<<a[i]<<" ";
                 }
       
          cout<<endl;

         cout<<"time = "<<time<<endl;
       }
            
	     break;
	     
       case 53:
            
            { srand((unsigned int)time(0)); 
             for(int i=0;i<size;i++)
              {
                a[i]=rand()%100; 
              }

               for(int i=0;i<size;i++)
                {
                  cout<<a[i]<<" ";
                }
     
          cout << endl;

                int time=GetTickCount(); 
                InsertSortVer2<T>(a, size); 
                time=GetTickCount()-time; 

                for(int i=0; i<size;i++)
                 {
                   cout<<a[i]<<" ";
                 }
       
          cout<<endl;

         cout<<"time = "<<time<<endl;
       }
            
	     break;
	     
       case 54:
            
            { srand((unsigned int)time(0)); 
             for(int i=0;i<size;i++)
              {
                a[i]=rand()%100; 
              }

               for(int i=0;i<size;i++)
                {
                  cout<<a[i]<<" ";
                }
     
          cout << endl;

                int time=GetTickCount(); 
                ShellSort<T>(a, size); 
                time=GetTickCount()-time; 

                for(int i=0; i<size;i++)
                 {
                   cout<<a[i]<<" ";
                 }
       
          cout<<endl;

         cout<<"time = "<<time<<endl;
       }
            
	     break;
	     
	   case 55:
            
            { srand((unsigned int)time(0)); 
             for(int i=0;i<size;i++)
              {
                a[i]=rand()%100; 
              }

               for(int i=0;i<size;i++)
                {
                  cout<<a[i]<<" ";
                }
     
          cout << endl;

                int time=GetTickCount(); 
               PyramidSort<T>(a, size); 
                time=GetTickCount()-time; 

                for(int i=0; i<size;i++)
                 {
                   cout<<a[i]<<" ";
                 }
       
          cout<<endl;

         cout<<"time = "<<time<<endl;
       }
            
	     break;
	     
       case 56:
            
            { srand((unsigned int)time(0)); 
             for(int i=0;i<size;i++)
              {
                a[i]=rand()%100; 
              }

               for(int i=0;i<size;i++)
                {
                  cout<<a[i]<<" ";
                }
     
          cout << endl;

                int time=GetTickCount(); 
               QuickSortVer1<T>(a, size); 
                time=GetTickCount()-time; 

                for(int i=0; i<size;i++)
                 {
                   cout<<a[i]<<" ";
                 }
       
          cout<<endl;

         cout<<"time = "<<time<<endl;
       }
            
	     break;
	     
	   case 57:
            
            { srand((unsigned int)time(0)); 
             for(int i=0;i<size;i++)
              {
                a[i]=rand()%100; 
              }

               for(int i=0;i<size;i++)
                {
                  cout<<a[i]<<" ";
                }
     
          cout << endl;

                int time=GetTickCount(); 
                QuickSortVer2<T>(a, size); 
                time=GetTickCount()-time; 

                for(int i=0; i<size;i++)
                 {
                   cout<<a[i]<<" ";
                 }
       
          cout<<endl;

         cout<<"time = "<<time<<endl;
       }
            
	     break;
	         
      }
    } 
                
               
}



int main()
{   cout<<"Neo...Wake up, Neo, and follow the white rabbit"<<endl;
    int choice;
    cout<<endl;
   
  cout << "1: int; 2: double; 3: char; 4: string" << endl;
  cin >> choice;

  switch(choice) {
    case 1:
      Work<int>;
      break;
    case 2:
      Work<double>;
      break;
    case 3:
      Work<char>;
      break;
    case 4:
      Work<string>;
      break;
     }
     }
   }