Problème de compréhension pour ce code

Logiciel & apps Programmation
1

Bonjour a tous :slight_smile:

J’ai un petit problème de compréhension pour ce code :

Le -1 de la boucle for (i = 0; i < tailleTableau-1; i++) sert a ne sortir du tableau car cette boucle parcourt le tableau donc le -1 est indispensable… j’ai compris c’est ok!

Mais le -1 de la boucle for (j = 0; j < tailleTableau-1; j++) ne sert a rien car cette boucle ne parcourt pas le tableau met permet de répéter la 1ere boucle… Alors pourquoi mettre le -1 dans cette boucle?


   1. int main(int argc, char *argv[])
   2. {
   3.     long tableau[10] = {2, 4, 3, 1, 15, 6, 9, 16, 19, 12};
   4.     long i = 0;
   5.    
   6.     ordonnerTableau(tableau, 10);
   7.
   8.     for(i = 0; i < 10; i++)
   9.     {
  10.         printf("%ld\n", tableau[i]);
  11.     }
  12.
  13.     return 0;
  14. }
  15.
  16.
  17. void ordonnerTableau(long tableau[], long tailleTableau)
  18. {
  19.     long i = 0, j = 0, a = 0;
  20.
  21.     for(j = 0; j < tailleTableau-1; j++)
  22.     {
  23.         for(i = 0; i < tailleTableau-1; i++)
  24.         {
  25.             if(tableau[i] > tableau[i+1])
  26.             {
  27.                 a = tableau[i+1];
  28.                 tableau[i+1] = tableau[i];
  29.                 tableau[i] = a;
  30.             }
  31.         }
  32.     }
  33. }
2

Tiens, on dirait un algorithme de tri, et à bulle qui plus est…

En fait l’idée c’est de faire remonter le minimum vers l’indice le plus bas (0), donc tu parcours une fois l’intégralité du tableau, puis une seconde fois pour l’algorithme en lui même.

Au passage, plutôt que :

ordonnerTableau(tableau, 10);

Utilise :

ordonnerTableau(tableau, sizeof(tableau)/sizeof(tableau[0]));

Et ainsi de suite, ce qui t’évitera des soucis.

3

Merci… mais tu répond pas a ma question…

4

Si. Mais il ne faut pas s’arrêter aux seuls bouts de code, mais lire tout le message.

5

Pour être sûr que ton tableau à X éléments soit complètement trié, il faut lancer X-1 fois la boucle i.

A partir de ce moment-là, le tableau étant déjà complètement trié, si tu lances de nouveau la boucle i, il sûr et certain qu’il n’y aura plus d’échanges. Ce ne serait qu’une perte de temps.

Il est donc inutile d’aller plus loin. C’est une optimisation du temps de tri.
 
Edité le 01/04/2010 à 01:47

6

Pour encore optimiser de plus le code tu peut même ajouter un autre critère d’arrêt, le role de la variable trouve : arrêter les boucles dès que le tableau sera trier.


void ordonnerTableau(long tableau[], long tailleTableau)
{
	long i = 0, j = 0, a = 0;
	int trouve = 1;
	for(j = 0; j < tailleTableau-1 && trouve; j++)
	{
		trouve = 0;
		for(i = 0; i < tailleTableau-1; i++)
		{
			if(tableau[i] > tableau[i+1])
			{
				a = tableau[i+1];
				tableau[i+1] = tableau[i];
				tableau[i] = a;
				trouve = 1;
			}
		}
	}
}

Edité le 03/04/2010 à 11:02

7

Je ne crois pas que ce soit le but du tri à bulle, non ?

8

Et pour encore optimiser plus on peut ajouter une variable pour ne balayer le tableau que jusqu’au rang du dernier échange du balayage précédent.

Et pour encore plus optimiser plus on peut balayer le tableau dans les deux sens altérnativement, tout en mémorisant le rang du dernier échange pour ne pas aller plus loin. :wink: