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.