Les tris en c
Contenu du snippet
c'est un script qui présente les trois méthode de tri (par extraction, à bulle et à deux) et leur temps de travail à partir d'un tableau d'entiers dont la taille est fixée par l'utilisateur
Source / Exemple :
#include <iostream.h>
#include <conio.h>
#include <dos.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/* realisé le 14/03/2003 par fred pour le tp n°7*/
/*titre: chronométrage du temps des trois méthodes de tris*/
initable( int tableau1[],int); /*declaration des fonctions*/
tri_extraction(int tableau2[],int);
void duree_t1_t2 (struct time t1, struct time t2);
tri_bulles(int tableau3[],int);
tri_deux(int tableau4[],int);
initable_ordonnee(int tab[],int taille);
main() /*fonction main*/
{
cout<<"\tLES DIFFERENTS TRIS ET LEUR TEMPS D'APPLICATION"<<endl<<endl;
/*-------------------------declaration des variables---------------------------------*/
int taille;
char reponse;
/*---------------------------nombre d'éléments---------------------------------------*/
do
{
cout << "\tentrez le nombre d'éléments du tableau: "; /*définition de la longueur du tableau */
cin >> taille;
int *tableau= new int[taille]; /* déclaration du tableau de longueur taille*/
struct time t1; /* déclaration des deux variables temps*/
struct time t2;
/*-------------------------appel des fonctions------------------------------------------*/
cout<<"\n\tinialisation du tableau de valeurs désordonnées"<<endl;
initable(tableau,taille);
/*-----------------------désordonné tri par extraction---------------------------------*/
cout<<"\ttri du tableau par extraction: appuyez sur entrée pour procéder"<<endl;
getch();
gettime(&t1); //temps t1 /* déclenchement du chrono*/
tri_extraction(tableau,taille);
gettime(&t2); //temps t2
cout<<endl<<endl;
cout<<"\taffichage du temps d'exécution de ce tri:appuyez sur entrée pour procéder"<<endl;
getch();
cout<<"\tle temps en heure, minute, seconde et centième est: "<<endl;
duree_t1_t2(t1, t2); //calcul de la durée t2-t1 /* appel à la fonction qui affiche la durée du tri*/
cout<<"\n\tinialisation du tableau de valeurs désordonnées"<<endl;
initable(tableau,taille);
/*-----------------------désordonné tri par à bulles------------------------------------*/
cout<<"\ttri du tableau par à bulles: appuyez sur entrée pour procéder"<<endl;
getch();
gettime(&t1); //temps t1 /* déclenchement du chrono*/
tri_bulles(tableau,taille);
gettime(&t2); //temps t2
cout<<endl<<endl;
cout<<"\taffichage du temps d'exécution de ce tri:appuyez sur entrée pour procéder"<<endl;
getch();
cout<<"\tle temps en heure, minute, seconde et centième est: "<<endl;
duree_t1_t2(t1, t2); //calcul de la durée t2-t1
cout<<"\n\tinialisation du tableau de valeurs désordonnées"<<endl;
initable(tableau,taille);
/*-----------------------désordonné tri par deux----------------------------------------*/
cout<<"\ttri du tableau par deux: appuyez sur entrée pour procéder"<<endl;
getch();
gettime(&t1); //temps t1 /* déclenchement du chrono*/
tri_deux(tableau,taille);
gettime(&t2); //temps t2
cout<<endl<<endl;
cout<<"\taffichage du temps d'exécution de ce tri:appuyez sur entrée pour procéder"<<endl;
getch();
cout<<"\tle temps en heure, minute, seconde et centième est: "<<endl;
duree_t1_t2(t1, t2); //calcul de la durée t2-t1
cout<<"\n\tinialisation du tableau de valeurs ordonnées"<<endl;
initable_ordonnee(tableau,taille);
/*------------------------ordonné tri par extraction-----------------------------------*/
cout<<"\ttri du tableau par extraction: appuyez sur entrée pour procéder"<<endl;
getch();
gettime(&t1); //temps t1 /* déclenchement du chrono*/
tri_extraction(tableau,taille);
gettime(&t2); //temps t2
cout<<endl<<endl;
cout<<"\taffichage du temps d'exécution de ce tri:appuyez sur entrée pour procéder"<<endl;
getch();
cout<<"\tle temps en heure, minute, seconde et centième est: "<<endl;
duree_t1_t2(t1, t2); //calcul de la durée t2-t1
cout<<"\n\tinialisation du tableau de valeurs ordonnées"<<endl;
initable_ordonnee(tableau,taille);
/*------------------------ordonné tri par bulles---------------------------------------*/
cout<<"\ttri du tableau par à bulles: appuyez sur entrée pour procéder"<<endl;
getch();
gettime(&t1); //temps t1 /* déclenchement du chrono*/
tri_bulles(tableau,taille);
gettime(&t2); //temps t2
cout<<endl<<endl;
cout<<"\taffichage du temps d'exécution de ce tri:appuyez sur entrée pour procéder"<<endl;
getch();
cout<<"\tle temps en heure, minute, seconde et centième est: "<<endl;
duree_t1_t2(t1, t2); //calcul de la durée t2-t1
cout<<"\n\tinialisation du tableau de valeurs ordonnées"<<endl;
initable_ordonnee(tableau,taille);
/*----------------------ordonné tri par deux---------------------------------------------*/
cout<<"\ttri du tableau par deux: appuyez sur entrée pour procéder"<<endl;
getch();
gettime(&t1); //temps t1 /* déclenchement du chrono*/
tri_deux(tableau,taille);
gettime(&t2); //temps t2
cout<<endl<<endl;
cout<<"\taffichage du temps d'exécution de ce tri:appuyez sur entrée pour procéder"<<endl;
getch();
cout<<"\tle temps en heure, minute, seconde et centième est: "<<endl;
duree_t1_t2(t1, t2); //calcul de la durée t2-t1
/*----------------------fin de programme--------------------------------------------------*/
cout<<"\tvoulez vous recommencer?"<<endl;
cout<<"\tapez o pour oui et n pour non"<<endl;
cin>>reponse;
}while(reponse!='n');
}
/*-----------------------------------------------------------------------------------------*/
initable(int tableau1[],int taille)
{
int i;
for(i=0;i<taille;i++)
{
tableau1[i]=random(1000)+1;
}
/* for(i=0;i<taille;i++)
{
cout<<tableau1[i]<<" "<<endl;
} */
}
/*----------------------------------------------------------------------------------------*/
initable_ordonnee(int tab[],int taille)
{
int i;
for(i=0;i<taille;i++)
{
tab[i]=random(1000)+1;
}
tri_extraction(tab,taille);
/* for(i=0;i<taille;i++)
{
cout<<tab[i]<<" "<<endl;
} */
}
/*---------------------------------------------------------------------------------------*/
tri_extraction(int tableau2[],int taille)
{
int i,j,tampon;
for(j=0;j<taille;j++)
{ /*quand tab[j](j=0) a ramassé le mini du tableau de valeurs tab[i]*/
for(i=j;i<taille;i++) /*on passe à tab[j+1] et on recommence une recherche de mini*/
{
if(tableau2[j]>tableau2[i])
{
tampon=tableau2[j];
tableau2[j]=tableau2[i];
tableau2[i]=tampon;
}
}
}
/* for(i=0;i<taille;i++)
{
cout<<tableau2[i]<<" "<<endl;
} */
}
/*---------------------------------------------------------------------------------------*/
tri_bulles(int tableau3[],int taille)
{
int i, tamp,rep;
while(rep)
{
rep=0; /*condition d'arret de la boucle*/
for(i=0;i<taille-1;i++)
{
if(tableau3[i]>tableau3[i+1]) // si besoins de trier alors permutation
{ //et retour au rang n-1 pour refaire
tamp=tableau3[i]; //une comparaison et ainsi de suite
tableau3[i]=tableau3[i+1];
tableau3[i+1]=tamp;
i--; //une permutation a été effectuée
rep=1; //donc le tableau n'est pas trié
} //pas de condition d'arret
}
}
}
/*------------------------------------------------------------------------------------------*/
tri_deux(int tableau4[],int taille)
{
int i,j ,tampon,rang=taille; /*on pousse le maxi en bout de tableau*/
while(rang!=0)
{
for(j=0;j<rang;j++)
{
if(tableau4[j]>tableau4[j+1])
{
tampon=tableau4[j+1];
tableau4[j+1]=tableau4[j];
tableau4[j]=tampon;
}
}
rang--; /* on recommence avec une case du bout du tableau en moins*/
}
/* for(i=0;i<taille;i++)
{
cout<<tableau4[i]<<" "<<endl;
} */
}
/*------------------------------------------------------------------------------------------*/
void duree_t1_t2 (struct time t1, struct time t2)
{
struct time t;
// printf est l'équivalent de cout avec formatage des données
printf("\tTemps t1 : %2d:%02d:%02d:%02d", t1.ti_hour, t1.ti_min, t1.ti_sec, t1.ti_hund);
printf("\n\tTemps t2 : %2d:%02d:%02d:%02d", t2.ti_hour, t2.ti_min, t2.ti_sec, t2.ti_hund);
if (t2.ti_hund < t1.ti_hund) //
{ t.ti_hund = t2.ti_hund+100-t1.ti_hund;
t2.ti_sec--; } //
// Calcul du nombre de centièmes
else //
t.ti_hund = t2.ti_hund-t1.ti_hund; //
if (t2.ti_sec < t1.ti_sec) //
{ t.ti_sec = t2.ti_sec+60-t1.ti_sec;
t2.ti_min--; } //
// Calcul du nombre de seconde
else //
t.ti_sec = t2.ti_sec-t1.ti_sec; //
if (t2.ti_min < t1.ti_min) //
{ t.ti_min = t2.ti_min+60-t1.ti_min;
t2.ti_hour--; } //
// Calcul du nombre de minutes
else //
t.ti_min = t2.ti_min-t1.ti_min; //
t.ti_hour = t2.ti_hour-t1.ti_hour; // Calcul du nombre d'heures
printf("\n\tDuree : %2d :%02d :%02d :%02d\n\n", t.ti_hour, t.ti_min, t.ti_sec, t.ti_hund);
}
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.