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.
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.