Discussion :

[racoboss]

Bonjour ,

je me retrouve confronter à un problème de compréhension au niveau de l algorithme du tri à bulles par odre croissant.
Dans la partie significative du code (ci dessous ) assurant l'inversion ,je ne comprend pas :
1-pourquoi on affecte à l' entier boucle la valeur nbreElem-1 (correpond au nombre d'éléments du tableau).
2-Pourquoi incrémenter boucle de -1 , je comprends bien que c' est pour sortir de la boucle while , mais pour moi cela signifie que meme lorsque le tri est réalisé , on continue à le trier??

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int boucle = nbElem -1  ;           // boucle pour le tri
      while (boucle >= 1){
         for (int i = 0 ; i <= boucle - 1 ; i++){
            if (tabEntier[i] > tabEntier[i+1]){
               // Inversion
               temp = tabEntier[i];
               tabEntier[i] = tabEntier[i+1];
               tabEntier[i+1] = temp;
            }         
         }
         boucle = boucle - 1;
      
         System.out.print("Contenu du tableau pendant le tri : ");
         for (int i = 0 ; i <= (tabEntier.length - 1); i++) {
            System.out.printf("%4d",tabEntier[i]);
         }
         System.out.println();      
      
      }

je vous remercie.

[jibbi]

Bonjour

1-pourquoi on affecte à l' entier boucle la valeur nbreElem-1

Puisque les valeur du tabEntier sont indexés de 0 à nbreElem -1.
La valeur de départ de boucle est l'index maximum du tableau. Par exemple, si nbreElem vaut 10 : l'index max est 9. Donc
int boucle = nbreElem -1; // soit 9 = 10 -1;

2-Pourquoi incrémenter boucle de -1

D'abord, on incrémente lorsqu'on additionne.
ici on soustrait 1 à boucle donc c'est plutôt décrémenter.

Voici ce qui ce passe dans le tri en bulle:
Les valeur cote-à-cote sont comparés jusqu'à index max ( boucle pour ton code).
La plus grande valeur est poussé en dernière position.
On recommence jusqu'à index max == 1 (boucle ==1 )

pour voir ce qui ce passe en temps réelle voir ce lien.

[racoboss]

Bonjour ,

je te remercie de ta réponse , il devait etre tard j ai bien compris aujourd hui.
Cependant , dans un tri a bulle "optimisé" que j' ai essayé de programmer ,je ne comprends pas pourquoi affecter la valeur false a inversion dans le programme ci dessous (en gras et rouge) , lorsque je retire cette instruction le programme est fonctionnel.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int boucle = nbElem - 1;           // boucle pour le tri
      boolean inversion = true;
      while ((boucle >= 1) && (inversion == true)) {
         inversion = false;
         for (int i = 0 ; i <= boucle - 1 ; i++){
            if (tabEntier[i] > tabEntier[i+1]){
               
              // Inversion
               temp = tabEntier[i];
               tabEntier[i] = tabEntier[i+1];
               tabEntier[i+1] = temp;
               inversion = true;
            }         
         }
         boucle = boucle - 1;
    }

merci de votre précieuse aide .

[jibbi]

je ne vois pas à quoi pourrait servir la variable inversion.
Il faudrait que tu développe d'avantage sur "l'optimisation" que tu recherche.

[droggo]

Siu,

Chercher à optimiser un tri à bulles, un des plus mauvais qui existe...

[racoboss]

je ne vois pas à quoi pourrait servir la variable inversion.
Il faudrait que tu développe d'avantage sur "l'optimisation" que tu recherche.

Bonsoir , je n' ai fait qu' appliquer le pseudo code de ton lien :

http://lwh.free.fr/pages/algo/tri/tri_bulle.htm

enfin , reveillons nous .

merci

[jibbi]

ha d'accord, je comprend. Mais ce n'est pas optimisé, c'est la même chose sauf qu'il faut une variable boolean en plus (et une boucle do-while() que j'aime pas trop). Je préfère ton code.

Je sais qu'il y a des variantes pour le tri à bulle, mais je ne sais si c'est vraiment plus rapide.

Chercher à optimiser un tri à bulles, un des plus mauvais qui existe...

Ce n'est pas l'un des plus rapide en effet.

Pour comparer les différents algorithme voir ici.
La page d'accueil.