Discussion :

[alcibiade]

Bonjour à tous,

Voici mon un petit code que j'ai trouvé sur le net et que j'ai modifié pour me satisfaire :

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
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
 
public class Tri{
 
public static void main(String [] args)
{
 
 
    int tabk[] = {1029,8,1,4,2,190,2999,90,3,0};
    int Exchange;
    int compteurA=0;
    int compteurB=0;
    int v=0;
 
     //Tri à bulles
    //BOUCLE A
    for(int a=0;a<N;a++)
    {  
            //BOUCLE B
            for(int b=0;b<N;b++)
            {  
	      //Echange des valeurs 
               if (tabk[a]<tabk[b])
               {  
                  Exchange=tabk[a]; 
                  tabk[a]=tabk[b];  
                  tabk[b]=Exchange; 
               } 
               //compte le nombre d'entrée dans la boucle b
               compteurB=compteurB +1;
            } 
 
            //compte le nombre d'entrée dans la boucle a
            compteurA=compteurA +1;
    }
    System.out.println("COMPTEUR A: "+compteurA);
    System.out.println("COMPTEUR B: "+compteurB);
 
     System.out.println(""); 
     //Affiche le tableau trié
     while(v<10)
    {
      System.out.println(tabk[v]);
      System.out.println(",");
      v++;
    }
}
}

Ce code fonctionne très bien et tri parfaitement mon tableau, le seul problème c'est qu'il ne ressemble pas du tout à un tri à bulles.
En effet un tri a bulles est censé comparé l'élément courant du tableau avec son successeur, soit tab[i]>tab[i+1]. Or là, on dirait qu'il compare l'élément courant avec chacun des éléments du tableau et cela à tour de rôle (La boucle B le fait).

De plus voici ce que me donne comme résultat les compteurA et compteurB :

Code :

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

1
2
3
 
COMPTEUR A: 10
COMPTEUR B: 100

Or il me semble bien que la compléxité d'un tel algo est O(n), soit n*n, mais 10 * 100 = 1000 !!! Dois-je comprendre par là que mon algo n'est pas un tri à bulles car sa complexité ne semble pas la même, ou bien, que tout simplement COMPTEUR B = 100 car 10*10 !?

Ma question est donc celle-ci, comment dois-je comprendre ce que j'ai codé ?

Je vous remercie d'avance de vos réponses et de vos éclaircissements.

[JoeChip]

Ma question est donc celle-ci, comment dois-je comprendre ce que j'ai codé ?

Si tu ne comprend pas ce code, c'est que tu ne l'as pas codé...

[benratti]

le seul problème c'est qu'il ne ressemble pas du tout à un tri à bulles.
En effet un tri a bulles est censé comparé l'élément courant du tableau avec son successeur, soit tab[i]>tab[i+1]. Or là, on dirait qu'il compare l'élément courant avec chacun des éléments du tableau et cela à tour de rôle (La boucle B le fait).

il ne s'agit effectivement pas d'un tri à bulles classique mais s'en rapproche tout de même. A chaque itération, les élements les plus petites sont remontés en début de tableau.

De plus voici ce que me donne comme résultat les compteurA et compteurB :

Code :

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

1
2
3
 
COMPTEUR A: 10
COMPTEUR B: 100

Or il me semble bien que la compléxité d'un tel algo est O(n), soit n*n, mais 10 * 100 = 1000 !!! Dois-je comprendre par là que mon algo n'est pas un tri à bulles car sa complexité ne semble pas la même, ou bien, que tout simplement COMPTEUR B = 100 car 10*10 !?

Ma question est donc celle-ci, comment dois-je comprendre ce que j'ai codé ?

Je vous remercie d'avance de vos réponses et de vos éclaircissements.

Il y a plusieurs erreurs dans ton raisonnement :

1. La complexité d'un tri à bulles est o(n^2) et non o(n)
2. Pour calculer une complexité, il faut compter les nombre d'opération couteuses, ici les permutations, pas forcement les comparaisons.
3. o(n^2) signifie que l'algo prendra k1 x n^2 + k2 x n + k3, où k1,k2 et k3 sont des constantes, c'est à dire que le temps d'execution est ploynomiale d'ordre 2 par rapport à n qui est ton nombre d'entrée.
   
   quand tu dis que o(n^2) correspondant à n x n, c'est faut, ca peut très bien correspondre à 10 x n x n, voir à 10 x n x n + 5000000 x n + 1209303... et ce n'est pas avec un seul test que tu vas pouvoir vérifier une complexité.

[alcibiade]

Merci pour votre réponse benratti, en effet ce n'est pas O(n) mais O(n * n). Petit erreur de ma part je l'avoue. Quand au tri je pense que je peux tout de même le classer dans "la famille" des tris à bulles vu que les nombres les plus grand remontent en haut petit à petit.

Quand à vous BenWillard relisez ma question, je dis dès la première phrase que j'ai repris le code sur le net et que je l'ai modifié. Je ne l'ai pas codé à 100 pour cent seul. De plus votre réponse ne sert à rien vu qu'elle ne m'aide nullement.

Merci tout de même.

[Fred_34]

Quand au tri je pense que je peux tout de même le classer dans "la famille" des tris à bulles vu que les nombres les plus grand remontent en haut petit à petit.

Pas trop d'accord avec toi, je ne pense pas que ce soit un tri à bulle.
A ce compte la, tous les tris seraient des tris à bulle car dans tous les tris, les nombres sont classés petit à petit...

Dans ton code, le compteur A n'est pas important, il est préférable de compter le nombre de comparaisons et le nombre de permutations :

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
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
public class Tri{
 
public static void main(String [] args)
{
 
    int tabk[] = { 1029, 8, 1, 4, 2, 190, 2999, 90, 3, 0 };
    int Exchange;
    int compteurTest = 0;
    int compteurEchange = 0;
    int v = 0;
 
    //Tri à bulles
    //BOUCLE A
    for (int a = 0; a < tabk.length; a++) {
      //BOUCLE B
      for (int b = 0; b < tabk.length; b++) {
        //Echange des valeurs 
        if (tabk[a] < tabk[b]) {
          Exchange = tabk[a];
          tabk[a] = tabk[b];
          tabk[b] = Exchange;
 
          //compte le nombre d'echange
          compteurEchange++;
 
        }
        //compte le nombre de test
        compteurTest++;
      }
    }
    System.out.println("COMPTEUR Test: " + compteurTest);
    System.out.println("COMPTEUR Echange: " + compteurEchange);
 
    System.out.println("");
    //Affiche le tableau trié
    while (v < tabk.length) {
      System.out.print(tabk[v]);
      System.out.print(",");
      v++;
    }
}
}

Pour ton tri, dans tout les cas, tu auras n^2 comparaisons.


Voici un exemple de tri à bulle

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
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
int tabk[] = { 1029, 8, 1, 4, 2, 190, 2999, 90, 3, 0 };
    int Exchange;
    int compteurTest = 0;
    int compteurEchange = 0;
    int v = 0;
 
    boolean encore;
 
    int N = tabk.length;
    do {
      encore = false;
 
      for (int i = 0; i < (N - 1); i++) {
        if (tabk[i] > tabk[i + 1]) {
          Exchange = tabk[i];
          tabk[i] = tabk[i + 1];
          tabk[i + 1] = Exchange;
          compteurEchange++;
          encore = true;
        }
        compteurTest++;
      }
      N--;
    }
    while (encore);
 
 
    System.out.println("COMPTEUR Test: " + compteurTest);
    System.out.println("COMPTEUR Echange: " + compteurEchange);
 
    System.out.println("");
    //Affiche le tableau trié
    while (v < tabk.length) {
      System.out.print(tabk[v]);
      System.out.print(",");
      v++;
    }

Dans ce tri, dans le pire des cas, il y aura (N-1)*(N/2) comparaisons.

[alcibiade]

Merci pour votre précieuse réponse Fred_34.

Votre solution fonctionne très bien. Donc d'après ce que j'ai compris ce n'est pas le nombre d'entré dans la boucle qui est important, mais le nombre d'opérations que l'on fait. C'est donc pour cela que la complexité au pire est de N*N (ou plutôt (n-1)*(n/2) comme dans votre exemple). Ce que je remarque aussi c'est que j'ai l'impression qu'à chaque fois qu'il y'a ce genre de complexité, il y'a une boucle imbriquée dans une autre. Ce qui explique bien le N*N justement.

Néanmoins il ne me reste plus que quelques questions encore :

• Si le précédent programme n'est pas un tri à bulles, qu'est-ce que c'est alors?
• Vous dites que la compléxité dans cet exemple est de N-1 *N/2. Je comprend bien pour quoi N-1 car si c'est N on serait mené à comparé N+1 à un moment et à sortir du tableau, mais pourquoi N/2. A aucun moment on ne divise le tableau. N-1*N/2 ne serait -il pas une complexité qui se raprocherai d'un tri dichotomique?

Merci encore pour votre patience.

[benratti]

Vous dites que la compléxité dans cet exemple est de N-1 *N/2. Je comprend bien pour quoi N-1 car si c'est N on serait mené à comparé N+1 à un moment et à sortir du tableau, mais pourquoi N/2. A aucun moment on ne divise le tableau. N-1*N/2 ne serait -il pas une complexité qui se raprocherai d'un tri dichotomique?

En fait, quand tu regardes la premiere itération de la boucle, tu vas faire N-1 comparaison. A la deuxième, ce sera N-2. et ainsi de suite.

Le nombre de comparaison que tu vas faire sera
(n-1) + (n-2) + ... + 1, soit la somme des entiers de 1 à (n-1), et cela est égale à n * (n-1) / 2, c'est juste mathématique.

C'est expliqué ici

[Rei Ichido]

Cela dit, on reste dans du O(n²), ce qui est plutôt lent.

Pour des tris rapides - en O(n.log(n)) en moyenne et dans le pire des cas - il faut aller vers le tri fusion ou, si on accepte le O(n²) dans certains cas, du quick sort.

[benratti]

Pour des tris rapides - en O(n.log(n)) en moyenne et dans le pire des cas - il faut aller vers le tri fusion ou, si on accepte le O(n²) dans certains cas, du quick sort.

C'est d'ailleurs le choix qui est pri dans l'API standard avec Collections.sort qui est un tri fusion légèrement modifé... mais il me semble qu'il s'agissait, dans le cadre de ce post, d'un cas d'école plus qu'une implémentation dans le cadre d'un réel projet.

[alcibiade]

Tout d'abord merci car j'ai compris beaucoup de choses grâce à vous et cela en peu de temps.

Il est vrai que l'exemple que j'ai pris n'est pas très pertinent pour trier des valeurs. Vous avez donc raison benratti, il s'agit donc d'un cas d'école. Pour l'explication du (n-1) * (n/2). J'ai vu ça en cours le jour ou vous avez postez votre réponse.

Bref je vous remercie encore. J'espère que tout ce dont nous avons parlé servira à d'autres.