Algorithmes de tris

Soyez le premier à donner votre avis sur cette source.

Vue 13 042 fois - Téléchargée 641 fois

Description

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

Codes Sources

A voir également

Ajouter un commentaire Commentaires
Messages postés
2
Date d'inscription
mercredi 20 octobre 2004
Statut
Membre
Dernière intervention
2 février 2006

Salut, je suis en train de me pencher sur les tris en ce moment et je suis tombé sur ta source, je m'interesse plus particulièrement au tri rapide.
Je ne sais pas si tu as trouvé ton erreur pour le décalage d'indice, mais le gros point fort du tri rapide est le pivot. Tu intègres pourtant dans ton code la position du pivot mais tout est fait comme si il etait forcément en première position, ton code ne marche donc pas dans toutes les situations. Une petite modif suffit, lorsque tu choisis ton pivot, tu le change de place avec le premier élément du tableau et tu commence ta partition du tableau après le pivot. il te suffit ensuite de replacer le pivot entre tes deux partitions. C'est une solution mais il en existe plein. Je pense que celle ci fonctionne, je ne l'ai pas testé mais sur papier ça a l'air de fonctionner, mais surtout tu as le choix du pivot sur la premiere partition, ça peut accelerer le calcul si sil est bien choisi (ex: pivot = valeur la plus proche de la valeur moyenne de tous le tableau).

void Echange (int Tab[], inti, int j)
{
int Temp = Tab[i] ;
Tab[i] = Tab[j] ;
Tab[j] = Temp ;
}

void TriRapide(int Tab[],int Debut, int p, int Fin)
{
int i, j, Temp, ValPivot = Tab[p] ;
if (Fin <= Debut) return() ;
if (p != Debut) Echange (Tab, p, Debut) ;
i = Début ;
j = Fin +1 ;
Do
{
while ((Tab[++i] < ValPivot) && (i <= Fin)) ;
while ((Tab[--j] > ValPivot) && (j > Debut)) ;
if (i < j) Echange(Tab, i, j) ;
}
while(i < j) ;
Echange(Tab, j, Debut)
TriRapide(Tab, Debut, Debut, j-1) ;
TriRapide(Tab, j+1, j+1, Fin) ;
}



A bientôt et si tu testes cette version, dis moi si ça marche !
Messages postés
4
Date d'inscription
vendredi 9 décembre 2005
Statut
Membre
Dernière intervention
27 septembre 2006

Merci de vos remarque les gars! ça me permet de mieux m'appliquer dans mes codes!
C'est vrai qu'a la limite elles sont choquantes, mais c'est indispensable:C'est à ça qu'on
reconnait des bons codeurs!
Messages postés
449
Date d'inscription
jeudi 26 août 2004
Statut
Membre
Dernière intervention
5 mars 2009

La demarche pour l'utilisateur est interessante mais ne doit pas se faire au detriment des codeurs qui sont les premiers vises et plus particulierment sur ce site....
on se dit sa surtout quand on voit ta fonction clignote() ...
Pour l'areation du code, c'est tres important et tres bien d'avoir cette notion en tete et de l'appliquer, mais il faut faire attention de ne pas enrumer quelqu'un avec un trop plein d'air !!! ;-)
Si jamais tu souhaite quand meme faire une belle presentation (ce qui est normal), regarde du cote de devcpp qui creer lui meme le squelette d'une application win32 et si tu veux garder un code portable, ba t'as qu'a taper dans le wxWindows qui est pas trop compliquer a digerer ou meme Qt qui est a mon avis encore plus simple.... regarde mes sources tu verras 2 exemples de bases d'utilisation de cette lib (frames, boutons, gestionnaire d'action, ...) et il y en a encore d'autre sur ce site.
Cela te permettra un code vachment plus sympa a regarder et qui aura un interet tout autre.... :-)

@++ et bon coding !
Messages postés
173
Date d'inscription
jeudi 20 décembre 2001
Statut
Membre
Dernière intervention
22 août 2008

Je veux pas faire le rabat joie, mais la console, tu peux la faire clignoter que tu veux, elle restera toujours moche :/
(oui je sais, t'as pas encore dépassé le stade de la console mais peu importe)
Par contre si tu veux progresser de manière utile, remplace cette infame fonction clignotte par,
for (int i = 0; i < 26;i++)
{
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);
}
Mais bon, c'est toujours pas ca :/
Sinon, plutot que de sauter une ligne entre chaque fonction, découpe ton programme en d'autres sous fonctions aux noms explicites ( genre lecture_tableau(), affiche_menu(), etc... )
comme ca tu gagneras en clarté
Messages postés
4
Date d'inscription
vendredi 9 décembre 2005
Statut
Membre
Dernière intervention
27 septembre 2006

Je suis conscient du fait que l'éfficacité passe avant le design! Mais un travail pas beau du tout ne vaut pas
un clou!Je me suis rendu compte que ce qui plait à l'utilisateur courant,c'est beaucoup plus la beauté...
C'est la raison pour laquelle j'essai autant que faire ce peut d'associer efficacité et design!
Et la fonction clignote donne un certain effet au programme.
Afficher les 9 commentaires

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.