Comparaison tri + test cpu

Commenter

Contenu du snippet

Code qui compare le bubble sort et le Quicksort avec : 1000, 5000, 10000, 15000, 20000, 25000, 30000 entiers.
Une fois les calculs fini, il est possible d'afficher le graphique de comparaison en pressant n'importe quelle touche.
Il est possible de changer l'echelle grace a la touche + et a la touche -.
Ce Programem permet de tester la vitesse de son CPU. Par exemple il me faut 20 secondes pour faire le tri bulle a 30000.

Source / Exemple : 


// 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;
	}	
}

Conclusion :


Il faut presser n'importe quelle touche avec l'executable fournie, ceci ce fait automatiquement avec le .cpp.

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.