Cet algo permet de comparer quelques tris de base (tri rapide, par insertion, par selection, par dénombrement)
Source / Exemple :
//**********************************************************************************
// Ce programme permet de comparer la complexit? des differents algorithmes de tris
// il a été écrit par NTCHANA NYAMSI ARLAIS
//**********************************************************************************
#include<stdlib.h>
#include<stdio.h>
#include<conio.h>
#include<dos.h>
#include<time.h>
#define N 4000
// nos d?clarations
int k,choix;
int tab[N],vect [N];
int longueur = 100;
int pas=200; // déclaration du pas
clock_t first, second; //Mesure du temps
//*******************************************************************************
// procédure affiche
// Permet d'afficher les valeurs du tableau
// (on vérifie avec cette proc?dure que le tableau est bien tri?)
//****************************************************************************************************
void affiche(int t[N],int max)
{
int m;
//clrscr();
for (m=0; m<max;m++) printf(" %4d",t[m]);
//getch();
}
//*************************************************************************************************
// proc?dure generervecteur
// Elle permet de remplir de mani?re al?atoire max +1 case d'un tableau de N ?l?ments
//*************************************************************************************************
void generervecteur(int tab[N],int longueur)
{
int i;
randomize();
for( i=0;i<longueur;i++)
{
tab[i]= /*i+1;*/ rand() % longueur;
}
}
//*************************************************************************************************
// procédure recopie
// Cette fonction permet de faire la copie d'un tableau ? un autre
//*************************************************************************************************
void recopie(int tab[N],int vect[N],int longueur)
{int i;
for(i=0;i<longueur+1;i++) vect[i]=tab[i];
}
//********************************************************************************************************
// procédure tris_rapide
//
// Le tri rapide est un algo bas? sur le paradigme "diviser pour regner" son temps d'?x?cution dans le pire
// des cas est O(ný). Par contre il est souvent le meilleur choix en pratique, ? cause de son efficacit?
// remarquable en moyenne : son temps d'?x?cution attendu est O(nln n)
//
//********************************************************************************************************
/**************** Ecriture de la proc?dure PARTITIONNER ******************************/
int PARTITIONNER (int tab[],int p,int r)
{
int i,j,x,temp,vrai = 1;
x = tab[p];
i = p-1;
j = r+1;
while (vrai/*vrai !=0*/)
{
do j --; while ( tab[j] > x );
do i++ ;while(tab[i] < x);
if (i<j)
{
temp = tab[i];
tab[i] = tab[j];
tab[j] = temp ;
}
else
{
vrai = 0;
return(j);
}
}
return(j);
}
//*********************** Ecriture de la proc?dure TRI RAPIDE *****************************************
void TRI_RAPIDE (int tab[N], int p ,int r)
{
int q;
if ( p < r )
{
q = PARTITIONNER (tab,p,r);
TRI_RAPIDE (tab, p, q);
TRI_RAPIDE (tab, q+1, r);
}
}
//*************************************************************************************************
// proc?dure TRI PAR INSERTION
//
// Le tri par insertion est un algorithme efficace quand il s'agit de trier un petit nombre d'?l?ments
// Le temp d'?x?cution dans le pire des cas est en O(n2)
//*************************************************************************************************
void TRI_INSERTION(int tab[],int longueur)
{
int j, cle, compt, vrai;
for(j=1;j<longueur;j++)
{
cle=tab[j];
//insertion de tab[j] dans la s?quence tri?e tab[0..j-2]
compt=j-1;
do
{
vrai=0;
if (tab[compt]>cle)
{
tab[compt+1]=tab[compt];
compt--;
vrai=1;
}
if (compt<0) vrai=0;
}
while(vrai);
tab[compt+1]=cle;
}
}
//*************************************************************************************************
// proc?dure tris par selection
//************************************************************************************************
void TRI_SELECTION(int tab[N])
{
int t[N],k,temp,i,j;
for(i=0;i<longueur;i++)
{
k=i;
for(j=i+1;j<longueur;j++)
{
if(tab[j]<tab[k]) k=j;
}
temp=tab[i];
tab[i]=tab[k];
tab[k]=temp;
}
};
//*************************************************************************************************
// proc?dure TRI PAR DENOMBREMENT
//
// Le principe du tri par d?nombrement est de d?terminer pour chaque ?lt x de l'entr?e, le nombre
// d'?lts inf?rieurs ? x. Cette information peut sevir ? placer l'?lt x directement ? sa position
// dans le tableau de sortie
// ce tri s'?x?cute en O(n) lorsque le plus grand ?lt k est tel que k=O(n)
//*************************************************************************************************
//************************ Algorithme qui recherche le max du tableau ******************************************
int CHERCHEMAX ( int tab[], int longueur)
{int i, temp = 0;
for (i=0; i<longueur; i++)
if (tab[i] > temp )
temp = tab[i];
return(temp);
}
//************************ Proc?dure TRI PAR DENOMBREMENT ******************************************
void TRI_DENOMBREMENT (int tab[],int tab2[],int k)
//tab[] tableau non tri?; tab2[] tableau qui au sortir de la proc?dure sera tri?; k plus grand entier
{int tab3[N]; int i,j;
for ( i=0; i<k+1; i++) tab3[i]=0;
for (j=0; j<longueur;j++) tab3[tab[j]]++;
// tab3[i] contient ? pr?sent le nombre d'?lt ?gaux ? i
for (i=1;i<k+1;i++) tab3[i] =tab3[i] +tab3[i-1];
//tab3[i] contient ? pr?sent le nombre d'?lts inf?rieurs ou ?gaux ? i
for (j = longueur-1 ; j >-1 ; j--)
{
tab2[tab3[tab[j]]-1] = tab[j];
tab3[tab[j]]--;
}
}
//**************************************************************************************************************************************
// fonction affichage entete
//**************************************************************************************************************************************
void affiche_entete( char * titre )
{
clrscr();
printf("NNAS*************************************************************************************************************************************************************************************** ");
textcolor(14 + 128 );
cprintf("| %s |",titre);
// delay(2000);
textcolor(15);
printf("**********************************************************************************************************************************************************************************************NNAS\n");
}
//**************************************************************************************************************************************
// fonction affichage menu accueil
//**************************************************************************************************************************************
void accueil(void)
{
printf(" \n \n \n \n \n\n\n\n\n");
printf(" ******************************************* \n");
printf(" * * \n");
printf(" * 1 TRIS PAR SELECTION * \n");
printf(" * * \n");
printf(" * * \n");
printf(" * 2 TRIS PAR INSERTION * \n");
printf(" * * \n");
printf(" * * \n");
printf(" * 3 TRIS PAR DENOMBREMENT * \n");
printf(" * * \n");
printf(" * * \n");
printf(" * 4 TRIS RAPIDE * \n");
printf(" * * \n");
printf(" * * \n");
printf(" * 5 COMPARAISON DES TRIS * \n");
printf(" * * \n");
printf(" * * \n");
printf(" * 0 EXIT * \n");
printf(" * * \n");
printf(" ******************************************* \n");
printf(" \n \n \n \n ");
}
//*************************************************************************************************************************
// proc?dure simule pour la pr?miere page
void simule(void)
{
clrscr();
textcolor(15);
printf(" \n \n \n \n \n\n\n\n\n");
printf(" \n \n \n \n \n\n\n\n\n");
printf("****************************************************************************** \n");
printf(" \n \n \n \n \n\n\n\n\n");
printf(" Ce programme permet de comparer la complexit? des differents algorithmes de tri \n");
printf(" \n\n");
printf(" il a ?t? ?crit par : ");
textcolor(15 + 128);
cprintf(" NNAS ");
printf(" \n \n \n \n \n\n\n\n\n");
printf("********************************************************************************");
}
//*************************************************************************************************************************************************************************
// Nom qui clignote
void clignote(int M)
{ // M temps d'un delay
clrscr();
textcolor(15);
printf(" \n \n \n \n\n\n\n\n\n\n\n\n\n\n \n\n\n\n\n");
printf("NTCHANA NYAMSI ARLAIS");
delay(M);
clrscr();
textcolor(15);
printf(" \n \n \n \n\n\n\n\n\n\n\n\n\n\n \n\n\n\n\n");
printf(" NTCHANA NYAMSI ARLAIS");
delay(M);
clrscr();
textcolor(15);
printf(" \n \n \n \n\n\n\n\n\n\n\n\n\n\n \n\n\n\n\n");
printf(" NTCHANA NYAMSI ARLAIS");
delay(M);
clrscr();
textcolor(15);
printf(" \n \n \n \n\n\n\n\n\n\n\n\n\n\n \n\n\n\n\n");
printf(" NTCHANA NYAMSI ARLAIS");
delay(M);
clrscr();
textcolor(15);
printf(" \n \n \n \n\n\n\n\n\n\n\n\n\n\n \n\n\n\n\n");
printf(" NTCHANA NYAMSI ARLAIS");
delay(M);
clrscr();
textcolor(15);
printf(" \n \n \n \n\n\n\n\n\n\n\n\n\n\n \n\n\n\n\n");
printf(" NTCHANA NYAMSI ARLAIS");
delay(M);
clrscr();
textcolor(15);
printf(" \n \n \n \n\n\n\n\n\n\n\n\n\n\n \n\n\n\n\n");
printf(" NTCHANA NYAMSI ARLAIS");
delay(M);
clrscr();
textcolor(15);
printf(" \n \n \n \n\n\n\n\n\n\n\n\n\n\n \n\n\n\n\n");
printf(" NTCHANA NYAMSI ARLAIS");
delay(M);
clrscr();
textcolor(15);
printf(" \n \n \n \n\n\n\n\n\n\n\n\n\n\n \n\n\n\n\n");
printf(" NTCHANA NYAMSI ARLAIS");
delay(M);
clrscr();
textcolor(15);
printf(" \n \n \n \n\n\n\n\n\n\n\n\n\n\n \n\n\n\n\n");
printf(" NTCHANA NYAMSI ARLAIS");
delay(M);
clrscr();
textcolor(15);
printf(" \n \n \n \n\n\n\n\n\n\n\n\n\n\n \n\n\n\n\n");
printf(" NTCHANA NYAMSI ARLAIS");
delay(M);
clrscr();
textcolor(15);
printf(" \n \n \n \n\n\n\n\n\n\n\n\n\n\n \n\n\n\n\n");
printf(" NTCHANA NYAMSI ARLAIS");
delay(M);
clrscr();
textcolor(15);
printf(" \n \n \n \n\n\n\n\n\n\n\n\n\n\n \n\n\n\n\n");
printf(" NTCHANA NYAMSI ARLAIS");
delay(M);
clrscr();
textcolor(15);
printf(" \n \n \n \n\n\n\n\n\n\n\n\n\n\n \n\n\n\n\n");
printf(" NTCHANA NYAMSI ARLAIS");
delay(M);
clrscr();
textcolor(15);
printf(" \n \n \n \n\n\n\n\n\n\n\n\n\n\n \n\n\n\n\n");
printf(" NTCHANA NYAMSI ARLAIS");
delay(M);
clrscr();
textcolor(15);
printf(" \n \n \n \n\n\n\n\n\n\n\n\n\n\n \n\n\n\n\n");
printf(" NTCHANA NYAMSI ARLAIS");
delay(M);
clrscr();
textcolor(15);
printf(" \n \n \n \n\n\n\n\n\n\n\n\n\n\n \n\n\n\n\n");
printf(" NTCHANA NYAMSI ARLAIS");
delay(M);
clrscr();
textcolor(15);
printf(" \n \n \n \n\n\n\n\n\n\n\n\n\n\n \n\n\n\n\n");
printf(" NTCHANA NYAMSI ARLAIS");
delay(M);
clrscr();
textcolor(15);
printf(" \n \n \n \n\n\n\n\n\n\n\n\n\n\n \n\n\n\n\n");
printf(" NTCHANA NYAMSI ARLAIS");
delay(M);
clrscr();
textcolor(15);
printf(" \n \n \n \n\n\n\n\n\n\n\n\n\n\n \n\n\n\n\n");
printf(" NTCHANA NYAMSI ARLAIS");
delay(M);
clrscr();
textcolor(15);
printf(" \n \n \n \n\n\n\n\n\n\n\n\n\n\n \n\n\n\n\n");
printf(" NTCHANA NYAMSI ARLAIS");
delay(M);
clrscr();
textcolor(15);
printf(" \n \n \n \n\n\n\n\n\n\n\n\n\n\n \n\n\n\n\n");
printf(" NTCHANA NYAMSI ARLAIS");
delay(M);
clrscr();
textcolor(15);
printf(" \n \n \n \n\n\n\n\n\n\n\n\n\n\n \n\n\n\n\n");
printf(" NTCHANA NYAMSI ARLAIS");
delay(M);
clrscr();
textcolor(15);
printf(" \n \n \n \n\n\n\n\n\n\n\n\n\n\n \n\n\n\n\n");
printf(" NTCHANA NYAMSI ARLAIS");
delay(M);
clrscr();
textcolor(15);
printf(" \n \n \n \n\n\n\n\n\n\n\n\n\n\n \n\n\n\n\n");
printf(" NTCHANA NYAMSI ARLAIS");
delay(M);
clrscr();
textcolor(15+128);
printf(" \n \n \n \n\n\n\n\n\n\n\n\n\n\n \n\n\n\n\n");
cprintf(" NTCHANA NYAMSI ARLAIS");
delay(M);
}
//*************************************************************************************************************************************************************************************
//
// DEBUT DU PROGRAMME PRINCIPAL
//
//*************************************************************************************************************************************************************************************
void main()
{char * titre;
simule();
getch();
clignote(700);
textcolor(15);
getch();
do{
clrscr();
titre= "MENU PRINCIPAL";
affiche_entete(titre);
accueil();
printf(" Votre choix : ");
scanf("%d",&choix);
// choix=getchar();
switch(choix)
{
case 1:
{
clrscr();first = 0;second = 0;
titre= " SELECTION ";
affiche_entete(titre);
printf(" \n \n \n");
// printf("Le tri par insertion est un algorithme efficace quand il s'agit de trier \n \nun petit nombre d'?l?ments ");
printf("\n\n");
// printf("Le temp d'?x?cution dans le pire des cas est en O(ný)");
// getch();
clrscr();
titre= " SELECTION ";
affiche_entete(titre);
printf(" \n\n\n\n");
printf("Entrer la taille du tableau et nous allons le remplir de fa?on al?atoire \n \n" );
printf(" \n\n");
printf("Taille : ");
// longueur = getchar();
scanf("%d",&longueur);
// printf(" le max est %d ",longueur);
//getch();
generervecteur(tab,longueur);
clrscr();
titre= " SELECTION ";
affiche_entete(titre);
printf(" \n\n\n\n");
printf("Le tableau avant le tri \n \n \n");
affiche(tab,longueur);
getch();
first = clock();
TRI_SELECTION(tab);
second = clock();
// clrscr();
// titre= " SELECTION ";
// affiche_entete(titre);
printf(" \n\n\n\n");
printf("Le tableau ? ?t? tri? en %f ms \n", (1000*second - 1000* first) / CLK_TCK);
getch();
printf(" \n");
printf("Le tableau tri? : \n");
printf("\n\n\n");
affiche(tab,longueur);
getch();
} break;
case 2:
{
clrscr(); first = 0;second = 0;
titre= " INSERTION ";
affiche_entete(titre);
printf(" \n \n \n");
printf("Le tri par insertion est un algorithme efficace quand il s'agit de trier \n \nun petit nombre d'?l?ments ");
printf("\n\n");
printf("Le temp d'?x?cution dans le pire des cas est en O(ný)");
getch();
clrscr();
titre= " INSERTION ";
affiche_entete(titre);
printf(" \n\n\n\n");
printf("Entrer la taille du tableau et nous allons le remplir de fa?on al?atoire \n \n" );
printf(" \n\n");
printf("Taille : ");
// longueur = getchar();
scanf("%d",&longueur);
// printf(" le max est %d ",longueur);
// getch();
generervecteur(tab,longueur);
clrscr();
titre= " INSERTION ";
affiche_entete(titre);
printf(" \n\n\n\n");
printf("Le tableau avant le tri \n \n \n");
affiche(tab,longueur);
getch();
first = clock();
TRI_INSERTION(tab,longueur);
second = clock();
// clrscr();
// titre= " INSERTION ";
// affiche_entete(titre);
printf(" \n\n\n\n");
printf("Le tableau ? ?t? tri? en %f ms \n", (1000*second - 1000* first) / CLK_TCK);
getch();
printf(" \n");
printf("Le tableau tri? : \n");
printf("\n\n\n");
affiche(tab,longueur);
getch();
} break;
case 3:
{
clrscr(); first = 0;second = 0;
titre= " DENOMBREMENT ";
affiche_entete(titre);
printf(" \n \n \n");
printf("Le principe du tri par d?nombrement est de d?terminer \n\npour chaque ?lt x de l'entr?e, le nombre d'?lts inf?rieurs ? x.\n\nCette information peut sevir ? placer l'?lt x directement ? sa position \n\ndans le tableau de sortie \n\nCe tri s'?x?cute en O(n) lorsque le plus grand\n\n?lt k est tel que k=O(n)");
printf("\n\n");
getch();
clrscr();
titre= " DENOMBREMENT ";
affiche_entete(titre);
printf(" \n\n\n\n");
printf("Entrer la taille du tableau et nous allons le remplir de fa?on al?atoire \n \n" );
printf(" \n\n");
printf("Taille : ");
// longueur = getchar();
scanf("%d",&longueur);
// printf(" le max est %d ",longueur);
// getch();
generervecteur(tab,longueur);
clrscr();
titre= " DENOMBREMENT ";
affiche_entete(titre);
printf(" \n\n\n\n");
printf("Le tableau avant le tri \n \n \n");
affiche(tab,longueur);
getch();
k = CHERCHEMAX ( tab , longueur);
first = clock();
TRI_DENOMBREMENT(tab,vect,k);
second = clock();
// clrscr();
// titre= " DENOMBREMENT ";
// affiche_entete(titre);
printf(" \n\n\n\n");
printf("Le tableau ? ?t? tri? en %f ms \n", (1000*second - 1000* first) / CLK_TCK);
getch();
printf(" \n");
printf("Le tableau tri? : \n");
printf("\n\n\n");
affiche(vect,longueur);
getch();
} break;
case 4:
{
clrscr(); first = 0;second = 0;
titre= " RAPIDE ";
affiche_entete(titre);
printf(" \n \n \n");
printf("Le tri rapide est un algo bas? sur le paradigme \" diviser pour regner \" \n \nSon temps d'?x?cution dans le pire des cas est O(ný). \n \nPar contre il est souvent le meilleur choix en pratique,\n\n? cause de son efficacit? remarquable en moyenne : son temps d'?x?cution \n\nattendu est O(nln n)");
printf("\n\n");
getch();
clrscr();
titre= " RAPIDE ";
affiche_entete(titre);
printf(" \n\n\n\n");
printf("Entrer la taille du tableau et nous allons le remplir de fa?on al?atoire \n \n" );
printf(" \n\n");
printf("Taille : ");
// longueur = getchar();
scanf("%d",&longueur);
// printf(" le max est %d ",longueur);
// getch();
generervecteur(tab,longueur);
clrscr();
titre= " RAPIDE ";
affiche_entete(titre);
printf(" \n\n\n\n");
printf("Le tableau avant le tri \n \n \n");
affiche(tab,longueur);
getch();
first = clock();
TRI_RAPIDE(tab,0,longueur);
second = clock();
// clrscr();
// titre= " RAPIDE ";
// affiche_entete(titre);
printf(" \n\n\n\n");
printf("Le tableau ? ?t? tri? en %f ms \n", (1000*second - 1000* first) / CLK_TCK);
getch();
printf(" \n");
printf("Le tableau tri? est le suivant : \n");
printf("\n\n\n");
affiche(tab,longueur);
getch();
} break;
case 5:
{
clrscr();
titre= "COMPARAISON DES TRIS";
affiche_entete(titre);
printf("-------------------------------------------------------------------------------\n");
printf("|");
textcolor(7);
cprintf("Taille"); printf(" |");
cprintf("Tri selection"); printf(" |");
cprintf("Tri insertion"); printf(" |");
cprintf(" Tri rapide"); printf(" |");
cprintf("Tri denombrement"); printf(" |\n");
textcolor(15);
printf("-------------------------------------------------------------------------------\n");
longueur = 100;
do
{
printf(": ");
///////////////////////////////////////////////////////////////
generervecteur(tab,longueur); recopie(tab,vect,longueur);
///////////////////////////////////////////////////////////////
//********************************************************************************************
// TRIS PAR SELECTION
first = 0;second = 0;
first =clock(); /* Gets system time */
TRI_SELECTION(vect);
second = clock(); /* Gets system time again */
printf("%4d : %-6e :",longueur,(1000*second - 1000*first) / CLK_TCK);
//********************************************************************************************
///////////////////////////////////////////
recopie(tab,vect,longueur);
//////////////////////////////////////////
//********************************************************************************************
// TRIS PAR INSERTION
first = 0;second = 0;
first = clock();
TRI_INSERTION( vect,longueur);
second = clock();
printf(" %-6e :",(1000*second - 1000*first)/CLK_TCK);
//********************************************************************************************
///////////////////////////////////////////
recopie(tab,vect,longueur);
//////////////////////////////////////////
//********************************************************************************************
// TRIS RAPIDE
first = 0;second = 0;
first = clock();
TRI_RAPIDE(vect,0,longueur);
second = clock();
printf(" %-6e :",(1000*second - 1000*first)/CLK_TCK);
//********************************************************************************************
///////////////////////////////////////////
recopie(tab,vect,longueur);
//////////////////////////////////////////
k=CHERCHEMAX(vect,longueur);
//********************************************************************************************
// TRIS PAR DENOMBREMENT
first = 0;second = 0;
first = clock();
TRI_DENOMBREMENT (vect,tab,longueur);
second = clock();
printf(" %-6e :",(1000*second - 1000*first) / CLK_TCK);
// printf(" %-6e :",(1000*second - 1000*first)/CLK_TCK);
printf("\n");
printf("-------------------------------------------------------------------------------\n");
//********************************************************************************************
longueur +=pas;
}
while(longueur<N);
getch();
} break;
case 0: choix = 0;break;
}
} while(choix != 0);
}
Conclusion :
Je me suis inspiré des manuels d'algorithmes pour sortir ces differets codes! jusqu'a present je suis à peu près sûr
que tous mes tris marchent excepté le tris rapide ou il y'a un décalage d'indice!
Si quelqu'un trouve la faille, prière de m'écrire à stephanearlais@yahoo.fr
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.