Discussion :

[lassault1]

Bonjour, oups tromper de forum



Je ne comprends pas les instructions de la fonction ordonnerTableau


Pouvez vous me commenter en détail si possible cette fonction ordonnerTableau?

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
int main(int argc, char *argv[])
{
    long tableau[10] = {2, 4, 3, 1, 15, 6, 9, 16, 19, 12};
    long i = 0;
 
    ordonnerTableau(tableau, 10);
 
    for(i = 0; i < 10; i++)
    {
        printf("%ld\n", tableau[i]);
    }
 
    return 0;
}
 
 
void ordonnerTableau(long tableau[], long tailleTableau)
{
    long i = 0, j = 0, a = 0;
 
    for(j = 0; j < tailleTableau-1; j++)
    {
        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;
            }
        }
    }
}

[Obsidian]

C'est une fonction censée trier ton tableau par ordre croissant, mais qui est intrinsèquement buguée et notoirement inefficace. Sa complexité est en O(n²).

D'abord, la boucle intérieure « i » compare chaque élément du tableau avec le suivant et les permute si le premier est supérieur au second. Seulement, en scannant toutes les positions, l'élément [i+1] se retrouve en dehors du tableau. Et s'il y a permutation, il risque d'y avoir corruption de la pile et tu vas te retrouver avec une belle segfault sans comprendre d'où elle vient.

Ensuite, le tableau n'est pas encore trié à ce stade : lorsque l'on permute deux chiffres, on ne sait pas si le plus petit n'est pas encore inférieur à un autre chiffre que l'on a déjà classé. Ton programme refait donc une passe. C'est le rôle de la boucle j. Comme, dans l'absolu, un nombre ne peut pas se déplacer plus de n fois, dans le cas où le plus petit nombre serait à la fin de ton tableau et qu'il remonterait, position par position, jusqu'à son début, on sait qu'en faisant n passes, le tableau sera forcément trié.

Sauf qu'avec 10 éléments, ça passe, mais avec un million d'éléments, et en considérant très largement que tu sois capable de permuter un million d'éléments par seconde, il te faudrait onze jours pour en venir à bout.


C'est à rendre pour quand ?

[Pouet_forever]

Seulement, en scannant toutes les positions, l'élément [i+1] se retrouve en dehors du tableau. Et s'il y a permutation, il risque d'y avoir corruption de la pile et tu vas te retrouver avec une belle segfault sans comprendre d'où elle vient.

Je pense que la fonction est correcte à ce niveau là. En effet, la variable va de i à 'tailleTableau-1' -1 donc il n'y a pas de dépassement.
Bon, il n'en est rien que je n'aime pas trop cette implémentation.

[Obsidian]

Si, si, regarde bien.

La fonction reçoit « 10 » en argument, soit la taille déclarée du tableau. Ensuite, « i » comme « j » courent bien de 0 à « tailleTableau-1 ». La cellule « tailleTableau-1 » est donc la dernière du tableau (les dix cellules sont numérotées de 0 à 9).

Comme, à l'intérieur de la boucle, on compare tableau[i] à tableau[i+1], il y aura bien un dépassement.

[Pouet_forever]

Non, justement elles vont de 0 à tailleTableau-2 (à cause du < ). Donc le i+1 ne fait pas de dépassement.
J'ai mis un coup de débuggeur pour être sûr de ce que je dis.

[lassault1]

Merci a vous, c'est plus clair..

Le -1 de la boucle for (i = 0; i < tailleTableau-1; i++) sert a ne pas sortir du tableau car cette boucle parcourt le tableau.

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?


Merci

[Obsidian]

Non, justement elles vont de 0 à tailleTableau-2 (à cause du < ). Donc le i+1 ne fait pas de dépassement.
J'ai mis un coup de débuggeur pour être sûr de ce que je dis.

Je m'incline ! C'est toi qui a raison, malgré deux relectures. Il faudra que je songe à poster plus tôt.

[Pouet_forever]

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?

Quand il te reste 1 seul élément de ton tableau à trier, tu penses que c'est nécessaire de faire quelque chose ?
Il est à sa place, donc pas besoin de continuer.

[lassault1]

Merci mais je comprends pas ce que tu veux dire pour le -1 de la boucle for (j = 0; j < tailleTableau-1; j++) ... peut tu est plus précis car je suis tout nouveau dans ce langage

Par contre le -1 de la boucle for (i = 0; i < tailleTableau-1; i++) j'ai compris car cela permet de ne pas sortir du tableau..

[Pouet_forever]

Ce n'est pas question de langage là.
Le but est de raisonner un peu. Le tri employé ici est le tri à bulles. La manière dont il est implémenté fait que tu parcours tailleTableau-1 fois ton tableau.
Tu passes par les 2 boucles, et au moment où tu arrives à tailleTableau-1 il ne te reste qu'un seul élément à trier, donc il est forcement à la bonne place ! (la dernière) donc pas besoin de continuer.

[lassault1]

Ce n'est pas question de langage là.
Le but est de raisonner un peu. Le tri employé ici est le tri à bulles. La manière dont il est implémenté fait que tu parcours tailleTableau-1 fois ton tableau.
Tu passes par les 2 boucles, et au moment où tu arrives à tailleTableau-1 il ne te reste qu'un seul élément à trier, donc il est forcement à la bonne place ! (la dernière) donc pas besoin de continuer.

Merci mais désolé pas compris ton explication..

Merci encore..

[lassault1]

Up.. personne peut m'aider..

[Pouet_forever]

Je suis désolé mais je ne vais pas pouvoir t'aider beaucoup plus.
Le plus simple pour que tu comprennes est que tu écrives toutes les étapes sur papier (avec un tableau de petite taille naturellement ). Tu visualiseras mieux les choses.

[lassault1]

J'ai deja fait sur papier..

T'es d'accord avec moi au moins que cette boucle (j = 0; j < tailleTableau-1; j++) ne parcourt pas le tableau mais elle sert a répéter la 2eme boucle?

[ok.Idriss]

Salut.

T'es d'accord avec moi au moins que cette boucle (j = 0; j < tailleTableau-1; j++) ne parcourt pas le tableau mais elle sert a répéter la 2eme boucle?

Elle parcours bien l'ensemble du tableau ...

Voici un algo du tri à bulle décroissant :

Code :

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

1
2
3
4
5
6
7
8
9
POUR i de 0 à (taille-1) FAIRE
     POUR j de (i+1) à (taille-1) FAIRE
          SI tab[j] >= tab[i] ALORS
               var <- tab[i]
               tab[i] <- tab[j]
               tab[j] <- var
           FIN SI
     FIN POUR
FIN POUR

Par exemple, pour un tableau tableau contenant les éléments {1,5,9,8,10} dans cet ordre, le tri se déroulera comme ceci :

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
 
1ère boucle, 1ère itération
5 1 9 8 10 (2ème boucle, 1ère itération)
9 1 5 8 10 (2ème boucle, 2ème itération)
9 1 5 8 10 (...)
10 1 5 8 9 
 
1ère boucle, 2ème itération
10 5 1 8 9 (2ème boucle, 1ère itération)
10 8 1 5 9 (...)
10 9 1 5 8 
 
1ère boucle, 3ème itération
10 9 5 1 8 (...)
10 9 8 1 5 
 
1ère boucle, 4ème itération
10 9 8 5 1 (...)

Cordialement,
Idriss

[lassault1]

Merci idriss.. mais comme tu as pas pris les même boucles que moi je ne peut pas comprendre

J'aimerais que tu utilise ce code pour m'expliquer que la boucle for(j = 0; j < tailleTableau-1; j++) parcours bien l'ensemble du tableau

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
    long i = 0, j = 0, a = 0;
 
    for(j = 0; j < tailleTableau-1; j++)
    {
        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;
            }
        }
    }
}

[ok.Idriss]

Ah zut, c'est par ordre croissant (mal lu), je modifie mon algo :

Code :

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

1
2
3
4
5
6
7
8
9
POUR i de 0 à (taille-1) FAIRE
     POUR j de (i+1) à (taille-1) FAIRE
          SI tab[j] <= tab[i] ALORS
               var <- tab[i]
               tab[i] <- tab[j]
               tab[j] <- var
           FIN SI
     FIN POUR
FIN POUR

Pour ton algo, il n'est pas optimisé, en reprenant l'exemple de tout à l'heure, voici comment il se comporte :

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
1ère boucle, 1ère itération 
1 5 9 8 10 (2ème boucle, 1ère itération)
1 5 9 8 10 (...)
1 5 8 9 10 
1 5 8 9 10 
 
(...)
1 5 8 9 10 (...) 
1 5 8 9 10 
1 5 8 9 10 
1 5 8 9 10 
 
(...)
1 5 8 9 10(...) 
1 5 8 9 10 
1 5 8 9 10 
1 5 8 9 10 
 
(...)
1 5 8 9 10(...) 
1 5 8 9 10 
1 5 8 9 10 
1 5 8 9 10

Tu as bien un tableau trié à chaque fois mais tu parcours inutilement le tableau ... Tu remarque que le nombre de ligne de chaque bloc (qui représentent les itérations de la première boucle) est de 4 (taille_tableau-1). Or c'est inutile de le parcourir depuis le début lorsque certains éléments ont déjà été triés.

Voici comment s'exécute l'algo que je viens de corrigé :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
1 5 9 8 10 
1 5 9 8 10 
1 5 9 8 10 
1 5 9 8 10 
 
1 5 9 8 10 
1 5 9 8 10 
1 5 9 8 10 
 
1 5 8 9 10 
1 5 8 9 10 
 
1 5 8 9 10

Le nombre d'itération de la seconde boucle diminue de 1 itération à chaque itération de la première boucle ... il est donc plus optimisé.

[lassault1]

Merci encore.. mais quand j'ai dis que j'aimerais que tu utilise ce code pour m'expliquer que la boucle for(j = 0; j < tailleTableau-1; j++) parcours bien l'ensemble du tableau, je voulais que tu utilise ce code : (car le tien dit que j = i+1

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
    for(j = 0; j < tailleTableau-1; j++)
    {
        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;
            }
        }
    }
}

Avec ce code même je veux STP que tu me dis pourquoi la boucle for(j = 0; j < tailleTableau-1; j++) parcours l'ensemble du tableau car pour moi elle sert a répéter la 2eme boucle..

[AI-Life]

Bonjour tout le monde.
Ce code là ne me plais pas vraiment, en effet le tri par bulles est très couteux c'est le cas le plus défavorable déconseillé.
si en examine de plus pré s code on voit qu'il entraine beaucoup d défauts de pages dans le cas ou le tableau est volumineux par exemple (je pense qu'il n'est pas performant tout simplement).
de plus je croix que la deuxième boucle pourra faire beaucoup plus d'itération inutiles.
je propose :

Code :

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

1
2
3
4
5
6
7
 
void ordonnerTableau(long tableau[], long tailleTableau)
{
       int permut = 0;
       while(!permut)
 
}

[AI-Life]

Bonjour tout le monde.
Ce code là ne me plais pas vraiment, en effet le tri par bulles est très couteux c'est le cas le plus défavorable déconseillé.
si en examine de plus pré s code on voit qu'il entraine beaucoup d défauts de pages dans le cas ou le tableau est volumineux par exemple (je pense qu'il n'est pas performant tout simplement).
de plus je croix que la deuxième boucle pourra faire beaucoup plus d'itération inutiles.
je propose pour un tri en bulles:

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
 
/* à ajouter dans le pré-processeur */
#define MAX 100 /* taille max d'un tableau elle peut changée */
#define true  1
#define false 0
//////////////////////////////////////////////////////////
void ordonnerTableau(long tableau[MAX], long tailleTableau)
{
       int permut = true , a , i;
       while(permut)
       {
              permut = false;
              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;
                             permut = true;
                      }
       }
}

je croix que c'est une solution optimale pour un tri par bulles (en fin je le croix) donnez votre avis n'hésitez pas à plus