COMPARAISON TRI + TEST CPU

// ex1.cpp : Defines the entry point for the console application.
//
//------------------------------------------------------------------------
//
//Spécifications:
//	   Finalité : Faire une application graphique de base pour tester la vitesse de son cpu et
//			comparer le tribulle et le quicksort
//			avec modification des graduations du repère pour zoomer en avant
//			et en arrière.
//    Précondition :
//	   Résultat :
//
//    Analyse :
//
//
//-----------------------------------------------------------------------
#include "stdafx.h"
#include <iostream> // fichier entête pour E/S en C++
#include <stdio.h>    // fichier entête pour E/S en C
#include <math.h>     // fichier entête pour fcts mathématiques
#include <conio.h>    // utile : fcts comme getch()
#include <stdlib.h>	  // fichier entête librairie standard (par ex:fct exit())
#include <time.h>
#include <iomanip>
#include "graphics.h"

using namespace std;

#define PI 3.1415926535  

int gradx=40;      //Unité du repère en x: 1 unité=80 pixels
int grady=40;		//Unité du repère en y: 1 unité=80 pixels

// fonction de traçage des axes et graduations
void traceAxes(int ax, int ay, int midx, int midy ); 

void Ini(int N, int *& TAB);
void tribulles(int* &TAB, int N ,int &nbpermutb);
void echanger(int* &TAB, int a,int b );
void aff(int *TAB, int N);
void Trirapide (int* TAB, int inf, int sup,int &nbpermutq);
void Segmentation (int* tab, int  inf, int  sup, int & place,int &nbpermutq);
void copieTAB (int* TAB, int* &TAB2, int N);
void CourbeB(int *& B,int Y);
void CourbeQ(int *& Q,int Y);
//void Ratio(int *& B,int *& Q,int Y);
void main(void)
{
	srand( (unsigned)time( NULL ) );
	int nbpermutb=0;//nombre de permutation avec le tri bulle
	int nbpermutq=0;//nombre de permutation avec le tri rapide
	double Tempsbul; //temps realise par le tribulles 
	double Tempsqck;//temps realise par le quicksort
	int * TAB;
	int * TAB2;
	int NN=7;
	int * B;
	B=new int[NN];
	 int * Q;
	Q=new int[NN];
	int cmp=0;
	for(int N=0;N<=30000;N=N+5000)
	{
		if(N==0)
			N=1000;

		Ini(N,TAB);
		copieTAB(TAB,TAB2,N);
		
		clock_t debbul =clock();//debut du chronometrage
		tribulles (TAB, N ,nbpermutb);//Appel du tribulles 
		clock_t finbul =clock();//fin du chronometrage
		Tempsbul=((double(finbul-debbul)));//en msecondes

		clock_t debqck =clock();//debut du chronometrage
		Trirapide (TAB2, 0, N-1,nbpermutq);//Appelle du quicksort
		clock_t finqck =clock();//fin du chronometrage
		Tempsqck=((double(finqck-debqck)));//en msecondes


		cout<<"N= "<<N<<endl;
		cout<<"Tri Bulles || Nbpermutation = "<<nbpermutb<<"  temps = "<< Tempsbul<<"ms"<<endl;
		cout<<"quicksort || Nbpermutation = "<<nbpermutq<<"  temps = "<< Tempsqck<<"ms"<<endl;
		cout<<endl;
		B[cmp]=nbpermutb;
		Q[cmp]=nbpermutq;

		if(N==1000)
			N=0;

		cmp++;
	}

	int gdriver = DETECT /* demande de détection automatique de la résolution de l'écran*/, gmode, errorcode;
	 int midx,midy,maxx,maxy;

	 int gradx=40;      //Unité du repère en x: 1 unité=80 pixels
	 int grady=40;		//Unité du repère en y: 1 unité=80 pixels
	 
	 cout<<"Press any key to show the Graphic<<endl;

	 char car;  scanf("%c",&car);  // utilisation de fonction de lecture du C  	  

	 // passage en mode graphique en demandant la détection automatique de 
	// la résolution de l'écran :
	 initgraph(&gdriver, &gmode,"");
	 errorcode = graphresult();
    if (errorcode != grOk){  /* an error occurred */
    	printf("Graphics error: %s\n", grapherrormsg(errorcode));
      printf("Press any key to halt:");
      getch();
      exit(1); /* terminate with an error code */
    }

	maxx=getmaxx();   maxy=getmaxy();   // détermination résolution de la fenêtre en nombre de pixels
	midx = maxx/ 2;midy = maxy/ 2;
	
	cleardevice();     // on efface la fenêtre graphique
	setcolor(WHITE);  // on sélectionne la couleur blanche
	
	char colstr[80];
	unsigned int Y=20000000;
	char c='a';//getch();//saisie de la premiere touche

	while( c!='q')
	{	cleardevice();
		
	
		if(c=='+')
		{
			Y=Y/2;
		}

		if(c=='-')
		{
			Y=Y*2;
		}
		if(Y<78125)
			Y=78125;
			
		if(Y>160000000)
			Y=160000000;
			
		setcolor(MAGENTA); 
		traceAxes(gradx,grady,midx, midy);	
 
		setcolor(WHITE);
		for(int k=0;k<=11;k++)
		{
			int ptt=maxy-30-k*grady;
			sprintf(colstr,"%i ",k*Y);
			outtextxy(0,ptt,colstr);
		}
		
		setcolor(RED);
		CourbeB(B,Y);//On trace la courbe tribulles
		setcolor(RED);
		sprintf(colstr, "Tribulles");//legende courbe tribulles
		outtextxy(100,10,colstr);
		//circle ( maxx-nbpermutb*grad,maxy-N*grad, 3);
		setcolor(YELLOW);
		CourbeQ(Q,Y);//On trace la courbe quicksort
		setcolor(YELLOW);
		sprintf(colstr, "Quicksort");//legende courbe quicksort
		outtextxy(220,10,colstr);
		setcolor(LIGHTMAGENTA);
		//Ratio(B,Q,Y);
		c=getch();
	}
	
	while (!kbhit()) ;   // boucle d'attente d'une touche , avant de fermer la fenêtre graphique
  	closegraph();  // pour fermer le mode graphique
  	exit(0);
}

void traceAxes(int ax, int ay, int midx, int midy)
{
	const int dec=5;  // nbre de pixels correspondant à la largeur d' 1 graduation
	int xcour,ycour;  // abscisse et ordonnee courante pour les graduations 
	int maxx=2*midx, maxy=2*midy;

	moveto(0,maxy-30);lineto(maxx,maxy-30);  // on trace l'axe horizontal
    line(midx-290,0,midx-290,maxy);            // on trace l'axe vertical

	// traçage des graduations sur l'axe des x (partie positive)
	for(xcour=midx;xcour>=0;xcour-=gradx)
	{line(xcour+30, midy+200-dec,xcour+30, midy+200+dec);}
	// traçage des graduations sur l'axe des x (partie negative)
	for(xcour=midx+gradx;xcour<=maxx;xcour+=gradx)	
	{line(xcour+30, midy+200-dec,xcour+30, midy+200+dec);}
	// traçage des graduations sur l'axe des y (partie positive)
	for(ycour=midy;ycour<=maxy;ycour+=grady)
	//Car on veux egalement tracer une graduation sur "l'ancien 0 de laxe centre"
    {line(midx-290, ycour-30,/*midx-290+dec*/maxx,ycour-30 );}
   	// traçage des graduations sur l'axe des y (partie negative)
	for(ycour=midy-grady;ycour>=0;ycour-=grady)
    {line(midx-290, ycour-30,/*midx-290+dec*/maxx,ycour-30 );}
}

void Ini(int N, int *& TAB)
{
	//int * TAB;
	TAB=new int[N];	

	for(int i=0;i<N;i++)
	{
		TAB[i]=rand()%99+1;
	}
}

void aff(int *TAB, int N)
{
	int i;
	for (i=0; i<N; i++)
		cout<< setw (2)<<  TAB[i]<< " " << flush ;
	cout<< endl << endl;
}

void echanger(int* &TAB, int a,int b )
{
	int temp;
	temp=TAB[a];
	TAB[a]=TAB[b];
	TAB[b]=temp;
}

void tribulles(int* &TAB, int N ,int &nbpermutb)
{
	nbpermutb=0;
	int i,j; 
	bool fini;
	i=0;
	do 
	{
		fini=true;
		for(j=0;j<N-i-1;j++)
		{
			if( TAB[j]>TAB[j+1])
			{
				echanger(TAB, j, j+1);
				nbpermutb++;
				fini=false;
			}
		}
		i++;
	}
	while (fini==false && i!=N-1);
}

void Trirapide (int* tab, int inf, int sup,int &nbpermutq)
{
	int place;
	if (inf<sup)
	{	
		Segmentation (tab, inf, sup, place,nbpermutq);
		Trirapide (tab, inf, place-1,nbpermutq);
		Trirapide (tab, place+1, sup,nbpermutq);
	}
}

void Segmentation (int* tab, int  inf, int  sup, int & place,int &nbpermutq)
{
	
	int i=sup;
	int pivot=inf;  


	do
	{
		if  ( tab[pivot]<tab[pivot+1] )
		{
			echanger (tab, pivot+1, i);
			i--;
			nbpermutq++;//cout << "permutation loc1, nbpermutq=" << nbpermutq <<endl;
		}
		else
		{
			echanger(tab, pivot, pivot+1);
			nbpermutq++;// cout << "permutation loc2, nbpermutq=" << nbpermutq << endl;
			pivot++;
		}
	}while (i!=pivot);
	place=pivot;
}

void copieTAB (int* TAB, int* &TAB2, int N)
{
	TAB2 =new int[N] ;
	int i;
	for (i=0; i<N; i++)
	{
		TAB2[i]=TAB[i];
	}
}

void CourbeB(int *& B,int Y)
{
	int maxx=getmaxx();   int maxy=getmaxy(); char colstr[80];
	setcolor(WHITE);
	int xcour=30;
	int ycour=maxy-30;
	int cmp=0;
	for(int N2=0;N2<=30000;N2=N2+5000)
	{
		if(N2==0)
			N2=1000;

		int pt=30+N2/50;
		setcolor(RED);
		line(xcour,ycour,pt,maxy-30-B[cmp]/Y*40);
		xcour=pt;
		ycour=maxy-30-B[cmp]/Y*40;
		cmp++;
		setcolor(WHITE);
		line(pt,maxy-30,pt,maxy-10); 
		sprintf(colstr,"N=%i ",N2);
		outtextxy(pt-45,maxy-11,colstr);
		
		if(N2==1000)
			N2=0;
	}
}

/*void Ratio(int *& B,int *& Q,int Y)
{
	int maxx=getmaxx();   int maxy=getmaxy(); char colstr[80];
	setcolor(WHITE);
	int xcour=30;
	int ycour=maxy-30;
	int cmp=0;
	for(int N2=0;N2<=30000;N2=N2+5000)
	{
		if(N2==0)
			N2=1000;

		int pt=30+N2/50;
		setcolor(LIGHTMAGENTA);
		line(xcour,ycour,pt,maxy-30-((B[cmp]+Q[cmp])/2)/Y*40);
		xcour=pt;
		ycour=maxy-30-(B[cmp]/Q[cmp])/Y*40;
		cmp++;
		
		if(N2==1000)
			N2=0;
	}
}*/

void CourbeQ( int *& Q,int Y)
{
	float maxxf=(float)getmaxx();   float maxyf=(float)getmaxy(); char colstr[80];
	int maxxi=getmaxx();   int maxyi=getmaxy();
	setcolor(WHITE);
	 float xcourf=30;
	 float ycourf=maxyf-30;
	int cmp=0;
	for( int N2=0;N2<=30000;N2=N2+5000)
	{
		if(N2==0)
			N2=1000;

		float ptxf=(float)(30+N2/50);
		float valtabf=(float)(Q[cmp]);
		float Yf=(float)(Y);
		float resf=(valtabf/Yf)*40;
	    float ptyf=maxyf-30-resf;
		int ptyi=(int)(ptyf);
		int ptxi=(int)(ptxf);
		setcolor(YELLOW);
		int xcouri=(int)(xcourf);
		int ycouri=(int)(ycourf);
		line(xcouri,ycouri,ptxi,ptyi);
		xcourf=ptxf;
		ycourf=ptyf;
		cmp++;
		setcolor(WHITE);
		line(ptxi,maxyi-30,ptxi,maxyi-10); 
		sprintf(colstr,"N=%i ",N2);
		outtextxy(ptxi-45,maxyi-11,colstr);
		
		if(N2==1000)
			N2=0;
	}	
}