#include<CONIO.H>
#include<IOSTREAM.H>
#include<STDLIB.H>
#include<STDIO.H>
//#include<IO.H>
//#include<fstream.h>
class sorting
{
public:
void  inser_sort(int a[],int n);            // tp perform insertion sort.
void  ins_sort(int a[],int n);
void  shell_sort(int a[],unsigned int n);   // to perform shell sort.
void  heap_sort(int a[],unsigned int n);
void  perc_down(int a[],unsigned int i,unsigned int n);
void  mergesort(int a[],unsigned int n);    // to perform merge sort.
void  merge(int a[],int tmp_array[],int l_pos,int r_pos,int right_end);
void  m_sort(int a[],int tmp_array[],int left,int right);
void  quick_sort(int a[],unsigned int n);   // to perform quick sort.
int   median3(int a[],int left,int right);  // to find the median.
void  q_sort(int a[],int left,int right);
void  swap(int &x,int &y);                  // to swap two numbers.
};
//=====================================
//		BUILDING  MEMBERS OF THE CLASS
//=====================================
void sorting::swap(int &x,int &y)
{
	int g;
	g=x;
	x=y;
	y=g;
}
//======================================
void sorting::inser_sort(int a[],int n)
{
 unsigned int j,i,p;
 int tmp;
 a[0]=-100;
 for (p=2;p<=n;p++)
 {
	tmp=a[p];
	for (j=p;tmp<a[j-1];j--)
		a[j]=a[j-1];
	a[j]=tmp;
 }
 for (i=1;i<=n;i++) cout<<"    "<<a[i]<<"\n";
}
//======================================
void sorting::ins_sort(int a[],int n)
{
 unsigned int j,i,p;
 int tmp;
 a[0]=-100;
 for (p=2;p<=n;p++)
 {
	tmp=a[p];
	for (j=p;tmp<a[j-1];j--)
		a[j]=a[j-1];
	a[j]=tmp;
 }

}//====================================

void sorting::shell_sort(int a[],unsigned int n)
{
	clrscr;
	char f;
	long int prod;
	unsigned int i,j,increment,r,k,w;
	int tmp,border,sum,s;border=0;prod=1;
	int *b;r=1;

	b=(int *) malloc((35) * sizeof(int));
	// TO FIND THE HIBBARD'S ARRAY FOR INCREMENTS.
	while (border < n)
	{
		prod=prod*2;
		sum=prod-1;
		border=sum;
		b[r]=border;
		r++;
	}

	r=r-2;

		for(k=r;k>0;k--)
		{
		increment=b[k];
		for(i=increment+1;i<=n;i++)
		{
			tmp=a[i];

			for(j=i;j>increment;j-=increment)
				if(tmp<a[j-increment])
					a[j]=a[j-increment];
				else

					break;
			a[j]=tmp;
		  }

	    }
       for (i=1;i<=n;i++)
		cout<<"   "<<a[i]<<"\n";
       delete(b);
 }

//=========================================
void sorting::perc_down(int a[],unsigned int i,unsigned int n)
{
	unsigned int child;
	int tmp;
	for (tmp=a[i];i*2<=n;i=child)
	{
		child=i*2;
		if((child !=n) && (a[child+1] > a[child]))
			child++;
		if (tmp <a[child])
			a[i]=a[child];
		else
			break;
       }
       a[i]=tmp;
}
//============================================

void sorting::heap_sort(int a[],unsigned int n)
{
	int i,g;
	for(i=n/2;i>0;i--)
		perc_down(a,i,n);
	for(i=n;i>=2;i--)
	{
		swap(a[1],a[i]);
		perc_down(a,1,i-1);
	}
	for(i=1;i<=n;i++)  cout<<"    "<<a[i]<<"\n";
}

//============================================
void sorting::merge(int a[],int tmp_array[],int l_pos,int r_pos,int right_end)
{
	int i,left_end,num_elements,tmp_pos;
	left_end=r_pos-1;
	tmp_pos=l_pos;
	num_elements=right_end-l_pos+1;
	//  main loop
	while((l_pos<=left_end) && (r_pos<=right_end))
		if(a[l_pos]<= a[r_pos])
			tmp_array[tmp_pos++] = a[l_pos++];
		else
			tmp_array[tmp_pos++] = a[r_pos++];
       while(l_pos<=left_end)  //copy the rest of the first half
		tmp_array[tmp_pos++] = a[l_pos++];
       while(r_pos <= right_end)  //copy the rest of the right end
		tmp_array[tmp_pos++] = a[r_pos++];
       // copy tmp_array back
       for(i=1;i<=num_elements;i++,right_end--)

		a[right_end] = tmp_array[right_end];

}
//===================================================
void sorting::m_sort(int a[],int tmp_array[],int left,int right)
{
	int center;
	if(left < right)
	{
		  center=(left+right)/2;
		  m_sort(a,tmp_array,left,center);
		  m_sort(a,tmp_array,center+1,right);
		  merge(a,tmp_array,left,center+1,right);
	}
}
//=====================================================
void sorting::mergesort(int a[],unsigned int n)
{
	int *tmp_array;
	int i;
	tmp_array=(int *) malloc ((n+1) * sizeof(int));
	if (tmp_array !=NULL)
	{
		m_sort(a,tmp_array,1,n);
		free(tmp_array);
		for(i=1;i<=n;i++)  cout<<"  "<<a[i]<<"\n";

	}
	else

			cout<<"NO SPACE FOR TMP AAAY !!!\n";

}
//======================================================
int sorting::median3(int a[],int left,int right)
{
	int center;
	center=(left+right)/2;
	if(a[left]> a[center])
		swap(a[left],a[center]);
	if(a[left]>a[right])
		swap(a[left],a[right]);
	if(a[center]>a[right])
		swap(a[center],a[right]);
	// invarient : a[left] <= a[center] <= a[right]
	swap(a[center],a[right-1]); // hide pivot
	return a[right-1];	      // return pivot

 }
//=======================================================
void sorting::q_sort(int a[],int left,int right)
{
	int i,j;
	int pivot;
	if(left+30 <= right)
	{

		pivot=median3(a,left,right);
		i=left;j=right-1;
		for(;;)
		{
			while(a[++i] < pivot);

			while(a[--j] > pivot);
			if(i < j)
				swap(a[i],a[j]);
			else
				break;
		}
		swap(a[i],a[right-1]);  // restore pivot

		q_sort(a,left,i-1);
		q_sort(a,i+1,right);
       }
}
//=================================================
void sorting::quick_sort(int a[],unsigned int n)
{
	int i;
	q_sort(a,1,n);
	ins_sort(a,n);
	for(i=1;i<=n;i++) cout<<"  "<<a[i]<<"\n";
}
//===================================================
//		THE MAIN BODY OF THE PROGRAM .
//===================================================
main()
{
	int  i,n,dat;
	int *a;
	sorting *sor;
	char ch,chr;
	FILE *p, *q;
 do
 {      clrscr();
	cout<<"                enter      size  \n" ;
	cin>>n;
	a=(int *) malloc((n+1) * sizeof(int));
	// TO WRITE ON A TEXT FILE RANDOM NUMBERS IN THE RANGE [1..N] .
	p = fopen("c:\RAND.DAT","w");   // TO OPEN THE FILE FO WRITING.

	for(i=1;i<=n;i++)
	{
		dat=random(n);         // TO ASSIGN DATA IN THE FILE.
		fprintf(p,"%d ",dat);
	 }                             // CLOSING THE FILE.
	 fclose(p);
	 // TO COPY THE DATA FROM THE FILE TO THA ARRAY A.
	 p = fopen("c:\RAND.DAT","r");  // TO OPEN THE FILE FOR READING.
	 i=1;
	do
	 {
		fscanf(p,"%d",&dat);    // READING DATA FROM THE FILE.
		a[i]=dat;
		i++;
	 }
	 while ( !feof(p) );
	 fclose(p);                     // CLOSING THE FILE.
	 clrscr();
	 for(i=1;i<=7;i++) cout<<"\n";
	 cout<<"		insertion   sort   :    press    1\n\n";
	 cout<<"                shell       sort   :    press    2\n\n";
	 cout<<"                heap        sort   :    press    3\n\n";
	 cout<<"                merge       sort   :    press    4\n\n";
	 cout<<"                quick       sort   :    press    5\n\n";
	 cin>>chr;
	 if(chr=='1') sor->inser_sort(a,n);
	 if(chr=='2') sor->shell_sort(a,n);
	 if(chr=='3') sor->heap_sort(a,n);
	 if(chr=='4') sor->mergesort(a,n);
	 if(chr=='5') sor->quick_sort(a,n);

         delete(a);
    cout<<"                    press         n   or  N  to stop \n";
    cout<<"	            else          press  any other key\n";
    ch=getche();
   }

	while ((ch !='n') && (ch !='N'));
	return 0;
}