#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<iostream.h>
#include<iomanip.h>
const n=100;
int s[n],q[n];
int co1=0,co2=0;
void mergesort(int low , int high);
void merge(int low , int mid , int high, int &co1);
void quicksort(int low , int high);
void partition(int low , int high , int &pivotpoint, int &co2);
void main()
{
   int i,j,low=0,high=n-1;
   FILE *fin,*fout;
   randomize();
   clrscr();
   fin = fopen ("in.txt" , "w");
   for(i=0;i<n;i++)
   {
      q[i]=s[i]=random(100);
      fprintf(fin, "%d", s[i]);
   }
   fclose(fin);
   printf("adade entekhabiye tasadofi");
   int co=0;
   cout<<"\n";
   for(i=0;i<n;i++)
   {
      if (co%10==0)
	 cout<<"\n";
      cout<<s[i]<<setw(4);
      co++;
   }
   mergesort(low,high);
   cout<<"\n\n\nadade moratab shode ba Merge Sort\n";
   fout = fopen ("out.txt" , "w");
   co=0;
   for(i=0;i<n;i++)
   {
      if (co%10==0)
	 cout<<"\n";
      cout<<s[i]<<setw(4);
      co++;
      fprintf(fout, "%d%c", s[i]);
   }
   fclose(fout);
   quicksort(low,high);
   cout<<"\n\nadade moratab shode ba Quick Sort\n";
   co=0;
   for(i=0;i<n;i++)
   {
      if (co%10==0)
	 cout<<"\n";
      cout<<q[i]<<setw(4);
      co++;
   }
   cout<<"\n\n\ntedad moghayeseye mergesort="<<co1<<"\n\ntedad moghayeseye quicksort="<<co2;
   getch();
}
//****************************************************
void mergesort(int low , int high)
{
   int mid;
   if (low<high)
   {
      mid=(low+high)/2;
      mergesort(low,mid);
      mergesort(mid+1,high);
      merge(low,mid,high,co1);
   }
}
//****************************************************
void merge(int low , int mid , int high, int &co1)
{
   int i=low,j=mid+1,k=low,a;
   int u[n];
   while(i<=mid && j<=high)
   {
      if(s[i]<s[j])
      {
	 u[k]=s[i];
	 i++;
      }
      else
      {
	 u[k]=s[j];
	 j++;
      }
      k++;
      co1++;
   }
   if(i>mid)
      for(a=j;a<=high;a++)
      {
	 u[k]=s[a];
	 k++;
      }
   else
      for(a=i;a<=mid;a++)
      {
	 u[k]=s[a];
	 k++;
      }
   for(a=low;a<=high;a++)
      s[a]=u[a];
}
//****************************************************
void quicksort(int low , int high)
{
   int pivotpoint;
   if (low<high)
   {
      partition(low,high,pivotpoint,co2);
      quicksort(low,pivotpoint-1);
      quicksort(pivotpoint+1,high);
   }
}
//****************************************************
void partition(int low , int high , int &pivotpoint, int &co2)
{
   int i,j,temp;
   int pivotitem;
   pivotitem=q[low];
   j=low;
   for(i=low+1;i<=high;i++)
   {
      if(q[i]<pivotitem)
      {
	 j++;
	 temp=q[i];
	 q[i]=q[j];
	 q[j]=temp;
      }
      co2++;
   }
   pivotpoint=j;
   temp=q[low];
   q[low]=q[pivotpoint];
   q[pivotpoint]=temp;
}