code pour ordonnerTableau n'est pas façile..

Version imprimable

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:

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;
            }
        }
    }
}

27/03/2010, 17h01
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 ?
27/03/2010, 23h36
Pouet_forever

Citation:

Envoyé par Obsidian

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.
28/03/2010, 00h27
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.
28/03/2010, 12h11
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. :aie:
28/03/2010, 12h32
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
28/03/2010, 12h40
Obsidian

Citation:

Envoyé par 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. :aie:

Je m'incline ! C'est toi qui a raison, malgré deux relectures. Il faudra que je songe à poster plus tôt.
28/03/2010, 12h51
Pouet_forever

Citation:

Envoyé par lassault1

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.
28/03/2010, 13h15
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..
28/03/2010, 14h58
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.
28/03/2010, 18h02
lassault1

Citation:

Envoyé par 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.

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

Merci encore..
29/03/2010, 13h36
lassault1

Up.. personne peut m'aider..
29/03/2010, 16h51
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 :aie: ). Tu visualiseras mieux les choses. ;)
29/03/2010, 17h31
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?

Salut.

Citation:

Envoyé par lassault1

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:

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:

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

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:

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;
            }
        }
    }
}

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

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:

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:

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é.

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:

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..

30/03/2010, 12h33
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:

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

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:

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:mouarf:) donnez votre avis n'hésitez pas:ccool: à plus