Tri à bulles

Invité · 04/11/2012, 15h01

Bonjour,

J'aimerais pouvoir trier un tableau avec la méthode du Tri à bulles, mais je ne sais pas comment m'y prendre, avec des conditions ?
Comment demander ensuite au programme 'inverser si nécessaire ?
Créer une fonction prévue pour ça ?

Merci,

Voici le code de ce que je veux 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
20
#include <stdio.h>
#include <stdlib.h>
 
int tableau[]={12,1,3,0,17,45,32,9};
 
void AfficheTableau();
int main()
{
    AfficheTableau();
    return 0;
}
void AfficheTableau()
{
    int i;
    for (i=0; i<8; i++)
    {
        printf("%d", tableau[i]);
    }
 
}

**Sve@r** · 04/11/2012, 15h15

Envoyé par emer62

Bonjour,

J'aimerais pouvoir trier un tableau avec la méthode du Tri à bulles, mais je ne sais pas comment m'y prendre, avec des conditions ?

Bonjour
Ben si t[i] > t[i+1] alors inverser t[i] et t[i+1]. Faire ça pour tous les i du tableau et recommencer tant qu'il y a eu au-moins une permutation...

Envoyé par emer62

Comment demander ensuite au programme 'inverser si nécessaire ?

Bah te suffit de créer une fonction cmp pouvant recevoir 2 éléments x et y et qui renvoie -1 si x < y et 1 si x > y
Ensuite au lieu de comparer t[i] et t[i+1] par une simple inégalité, tu demandes si cmp(t[i], t[i+1]) > 0.
Et quand tu veux inverser le tri, te suffit de modifier cmp en lui faisant renvoyer 1 si x < y et -1 si x > y.
Ou mieux, tu passes à cmp un 3° paramètre indiquant si tu veux une comparaison naturelle ou inversée et tu lui fais renvoyer -1 ou 1 en fonction de x, y et ce 3° paramètre...

Envoyé par emer62

Créer une fonction prévue pour ça ?

Oui, c'est le principe de la programmation structurée. Tu découpes ton travail en tâches élémentaires facilement adaptables/ajustables (comme ma fonction cmp)...

Envoyé par emer62

Voici le code de ce que je veux 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
20
#include <stdio.h>
#include <stdlib.h>
 
int tableau[]={12,1,3,0,17,45,32,9};
 
void AfficheTableau();
int main()
{
    AfficheTableau();
    return 0;
}
void AfficheTableau()
{
    int i;
    for (i=0; i<8; i++)
    {
        printf("%d", tableau[i]);
    }
 
}

Mouais. Eviter les variables globales serait déjà un bon point de départ dans l'apprentissage intelligent de la programmation structurée...

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
#include <stdio.h>
#include <stdlib.h>
 
void AfficheTableau(int [], int);
 
int main()
{
    int tableau[]={12,1,3,0,17,45,32,9};
    AfficheTableau(tableau, 8);
    return 0;
}
void AfficheTableau(int t[], int s)
{
    int i;
    for (i=0; i<s; i++)
    {
        printf("%d", t[i]);
    }
 
}

**Pouet_forever** · 04/11/2012, 15h17

Il faut que tu essayes de raisonner à comment tu le ferais 'en vrai'. Tu as des pièces de monnaies devant toi et tu essayes de les classer par ordre croissant en utilisant le tri à bulles (et comme si tu étais un programme).

Pour voir si tu dois inverser 2 pièces, il faut que tu regardes la valeur des 2, que tu choisisses celle qui a la plus faible/haute valeur (en fonction du tri) et que tu les inverse si nécessaire.

Est-ce que tu as compris le principe du tri à bulles ? =)

Invité · 06/11/2012, 20h10

Bonsoir,

Merci pour les réponses, précises et rapides, excellent ce forum.

Mais je ne comprends pas grand-chose...

Qu'est-ce qu'une comparaison naturelle ? Inversé ?

Pourquoi travailler avec 1 et/ou -1 ?

J'ai essayer de faire mon code (une partie) dites moi ce que vous en pensez :

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
#include <stdio.h>
#include <stdlib.h>
 
 
void AfficheTableau(int [], int);
int main()
{
    int tableau[]={12,1,3,0,17,45,32,9};
    AfficheTableau(tableau, 8);
    triabulle();
    return 0;
}
void AfficheTableau(int t[], int s)
{
    int i;
    for (i=0; i<s; i++)
    {
        printf("%d", t[i]);
    }
 
}
void triabulle (int t[i], t[i+1])
{
    if(t[i]<t[i+1])
    {
 
    }
}

**Sve@r** · 06/11/2012, 22h39

Envoyé par emer62

Qu'est-ce qu'une comparaison naturelle ? Inversé ?

J'ai employé ces termes pour illustrer une notion et non pas comme un terme technique.
Une comparaison naturelle c'est indiquer à l'ordinateur que 4 doit être placé avant 5, comme le fait notre cerveau de façon naturelle et qui te donne en final, si tu l'appliques sur chaque élément du tableau, un tableau trié dans l'ordre croissant.
Une comparaison inversée c'est indiquer à l'ordinateur que 4 doit être placé après 5, ce qui va à l'inverse de notre logique naturelle mais qui te donne en final un tableau trié dans l'ordre décroissant...

Envoyé par emer62

Mais je ne comprends pas grand-chose...Pourquoi travailler avec 1 et/ou -1 ?

Il faut bien que la fonction renvoie un indicateur indiquant comment est x par rapport à y (mal placé ? bien placé ?). Et comme le C ne travaille qu'avec des nombres...

Envoyé par emer62

J'ai essayer de faire mon code (une partie) dites moi ce que vous en pensez :

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
#include <stdio.h>
#include <stdlib.h>
 
 
void AfficheTableau(int [], int);
int main()
{
    int tableau[]={12,1,3,0,17,45,32,9};
    AfficheTableau(tableau, 8);
    triabulle();
    return 0;
}
void AfficheTableau(int t[], int s)
{
    int i;
    for (i=0; i<s; i++)
    {
        printf("%d", t[i]);
    }
 
}
void triabulle (int t[i], t[i+1])
{
    if(t[i]<t[i+1])
    {
 
    }
}

Mouais. On va éliminer ce qui vient de moi et on regarde ce qui reste: pas grand chose...
Déjà il me semble urgent que tu revoies les bases du C (tu remarqueras que j'emploie par charité le verbe "revoir" présumant que tu les sais déjà mais j'ai un gros doute à ce sujet). Tu remarques que la fonction "triabulle" est faite pour recevoir 2 paramètres mais tu l'appelles sans rien lui passer.
Ensuite si je devais écrire une fonction triabulle sensée trier tout un tableau, je lui ferais au-moins travailler sur ledit tableau. Là cette fonction ne fait que comparer 2 éléments...

Donc d'abord apprendre le principe le plus basique du tri à bulle

Code :

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

1
2
3
4
5
6
7
8
9
faire
    bad=0 
    pour i=1 jusqu au dernier i du tableau, faire
        si t[i-1] est mal placé par rapport à t[i] alors
            inverser t[i-1] et t[i]
            bad=1
        fin si
   fin pour
tant que bad=1 recommencer

Tu remarqueras que j'ai pas écrit "t[i-1] < t[i] mais "t[i-1] mal placé par rapport à t[i]" ce qui signifie que tu es libre de coder toi-même la notion "bien placé/mal placé" => d'où ma fonction cmp() facilement modifiable quand on veut faire évoluer cette notion...

PS: tu as fait ce que Pouet_forever a dit ? Tu as essayé de trier 7 ou 8 pièces en les regardant comme un ordinateur (une par une ou, pour le cas ici, 2 par 2) ???

Invité · 07/11/2012, 14h04

Bonjour,

Merci pour la réponse et donc si je veux revoir les conditions par exemple, ou puis-je en trouver sur le site ?

Je tourne en rond, ils n'en parlent nul par dans les tutoriels...

Invité · 07/11/2012, 14h26

J'ai trouvé se que je cherchais, je travaille dessus cette après-midi et vous en reparle ce soir, merci.

Invité · 07/11/2012, 17h22

Pas facile dis donc !

J'ai ajouté du code, sans vraiment savoir ce que je faisais...

J'ai également commencer à analyser 0 avec 1, car si je ne me trompe pas, un tableau commence par 0 en C...

J'ai créé une fonction cmp mais ça ne compare que les deux premiers nombres...

Enfin voilà, avis au critiques, merci :

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
#include <stdio.h>
#include <stdlib.h>
 
 
void AfficheTableau(int [], int);
int main()
{
    int tableau[]={12,1,3,0,17,45,32,9};
    AfficheTableau(tableau, 8);// ici le tableau non trié s'affiche
    compt(tableau, 8);// comparaion,
    triabulle();// puis tri
    AfficheTableau(tableau, 8);// Et enfin, le tableau trié s'affiche
    return 0;
}
void AfficheTableau(int t[], int s)
{
    int i;
    for (i=0; i<s; i++)
    {
        printf("%d", t[i]);
    }
 
}
void triabulle (int t[i], t[i])
{
    int bad=0;
    for(i=1; i)
    do
        {
            t[i=0]=t[i=1]//ici, inversion avec une condition
        }
    while(bad=1);//si bad vaut 1 alors il faut recommencer
}
void cmp(t[i]=0], t[i=1])//Ma fonction prévu uniquement pour comparer deux nombres
{
    if (t[i=0]>t[i+&])
    bad = 1
}

**Kirilenko** · 07/11/2012, 18h03

Il compile, ton code ?

Tu devrais peut-être revoir les bases : des conditions aux fonctions, en passant par les tableaux. Là, il y a beaucoup d'erreurs.

**Sve@r** · 07/11/2012, 18h23

Envoyé par emer62

Pas facile dis donc !

Ben arrivé ici, je ne sais plus trop si
1) tu es un néophyte désireux d'apprendre le C
2) tu es un étudiant en programmation C qui a déjà des bases et qui a un TP à faire
Si tu es 1), alors aussi honorable que cela soit, tu t'attaques à un morceau un peu difficile. Si tu es 2) alors là c'est gravissime. Parce qu'écrire t[i=0]...

Envoyé par emer62

J'ai ajouté du code, sans vraiment savoir ce que je faisais...

Ce qui renforce ma problématique...

Envoyé par emer62

J'ai également commencer à analyser 0 avec 1, car si je ne me trompe pas, un tableau commence par 0 en C...

Exact. Tu remarqueras d'ailleurs que j'ai adapté mon algo (dans mon post précédent) au C en faisant partir i à 1 et en comparant t[i] avec t[i-1] (plus facile en C d'aller de 1 au dernier que de 0 à l'avant dernier)

Envoyé par emer62

J'ai créé une fonction cmp mais ça ne compare que les deux premiers nombres...

Oui, c'est son but. Elle doit indiquer si le nombre 1 (qu'on peut appeler x) est bien ou mal placé par rapport au nombre 2 (qu'on peut appeler y). Ensuite, bien ailleurs dans le code (et de façon logique, dans une partie de l'algo située au dessus), il y aura une fonction qui se chargera d'appeler cmp() pour chaque t[i-1] et t[i] du tableau et qui, en fonction du résultat, se chargera d'intervertir ou pas t[i] et t[i-1]. Donc cmp n'a pas besoin d'autre chose que de 2 nombres à comparer (principe d'atomicité des fonctions)...

Envoyé par emer62

Enfin voilà, avis au critiques, merci :

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
#include <stdio.h>
#include <stdlib.h>
 
 
void AfficheTableau(int [], int);
int main()
{
    int tableau[]={12,1,3,0,17,45,32,9};
    AfficheTableau(tableau, 8);// ici le tableau non trié s'affiche
    compt(tableau, 8);// comparaion,
    triabulle();// puis tri
    AfficheTableau(tableau, 8);// Et enfin, le tableau trié s'affiche
    return 0;
}
void AfficheTableau(int t[], int s)
{
    int i;
    for (i=0; i<s; i++)
    {
        printf("%d", t[i]);
    }
 
}
void triabulle (int t[i], t[i])
{
    int bad=0;
    for(i=1; i)
    do
        {
            t[i=0]=t[i=1]//ici, inversion avec une condition
        }
    while(bad=1);//si bad vaut 1 alors il faut recommencer
}
void cmp(t[i]=0], t[i=1])//Ma fonction prévu uniquement pour comparer deux nombres
{
    if (t[i=0]>t[i+&])
    bad = 1
}

Bon, là tu mérites un coup de pouce parce que écrire t[i=0]>t[i+&] c'est que tu en as vraiment besoin

Exemple de cmp et de son utilisation

Code c :

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
int cmp(int x, int y)
{
    if (x < y) return -1;
    if (x > y) return 1;
    return 0;
}
 
void triabulle(...)
{
    ....
    ....
    ....
    if (cmp(t[i-1], t[i]) > 0)
    {
        // Interversion
        tmp=t[i-1];
        t[i-1]=t[i];
        t[i]=tmp;
 
        /* Si tu aimes les maths, tu pourras calculer (niveau 3°) qu'on peut aussi intervertir 2 int de cette façon
           t[i-1]=t[i-1]^t[i];
           t[i]=t[i-1]^t[i];
           t[i-1]=t[i-1]^t[i];
          Ce qui évite une variable intermédiaire mais faut savoir ce qu'est l'opérateur "^"...    */
    }
    ....
    ....
    ....
}

Invité · 07/11/2012, 20h42

Bonsoir,

Eh bien je suis les deux, j'avais commencé la programmation chez moi, seul, cela allais à peut près, mais depuis que je me suis mis à faire ce BTS... Je m'en écœure un peu faut dire...

Oui, c'est un TP.
En réalité, j'ai mis ça pour mettre quelques choses... je reconnais.

Je revois tout cela et vous en reparle dès que je suis bloqué (ou que j'y arrive, qui sait).

Quoi qu'il en soit, merci pour l'aide !

Enfin attention, la ligne if (t[i=0]>t[i+&])
C'est parce que je suis sur un pc portable, j'ai donc du oublier d'appuyer sur Maj pour faire le 1.
Je voulais donc mettre :

if (t[i=0]>t[i+1])

Autre chose : Qu'est-ce que tmp ? N'est-ce pas plutôt cmp ?

// Interversion
tmp=t[i-1];
t[i-1]=t[i];
t[i]=tmp;

Autre question : Pourquoi faudrait-t-il par logique mettre la fonction cmp en haut ?

**Sve@r** · 07/11/2012, 22h41

Envoyé par emer62

Bonsoir,

Eh bien je suis les deux, j'avais commencé la programmation chez moi, seul, cela allais à peut près mais depuis que je me suis mis à faire ce BTS... Je m'en écœure un peu faut dire...

Mouais. Peut-être (re)lire un bon tuto C...

Envoyé par emer62

Enfin attention, la ligne if (t[i=0]>t[i+&])
C'est parce que je suis sur un pc portable, j'ai donc du oublier d'appuyer sur Maj pour faire le 1.
Je voulais donc mettre :

if (t[i=0]>t[i+1])

Ok. Mais t[i=0] n'est pas une instruction super classe.
Cela commence par mettre i à 0 puis, cette affectation renvoyant un nombre (ici 0) ce nombre est alors utilisé comme indice de t[].
Bref c'est comme si t'écrivais i=0; if (t[i] > t[i+1]) mais en moins clair et comme ça remet i à 0 à chaque fois tu répètes sans cesse if (t[0] > t[1]) ce qui n'est pas pratique quand on se dit qu'il y a encore t[2], t[3], ...

Invité · 08/11/2012, 12h58

concernant tmp, il y a bien une erreur de frappe ? C'est bien cmp ?

**Sve@r** · 08/11/2012, 18h25

Envoyé par emer62

Autre chose : Qu'est-ce que tmp ? N'est-ce pas plutôt cmp ?

// Interversion
tmp=t[i-1];
t[i-1]=t[i];
t[i]=tmp;

Non, il s'agit d'une variable "en plus" pour conserver temporairement l'une des deux variables pendant qu'on la permute avec l'autre. Parce que lorsqu'on copie t[i] dans t[i-1] l'ancienne valeur de t[i-1] est alors perdue...
Punaise si tu confonds "variable" et "fonction" c'est que t'as plus que des lacunes en C (voire même en programmation en général)...

Envoyé par emer62

Autre question : Pourquoi faudrait-t-il par logique mettre la fonction cmp en haut ?

Le C veut absolument qu'une fonction soit connue avant d'être utilisée. Donc en écrivant le code de cmp() en premier, elle est alors connue et, plus tard, je peux l'utiliser dans la fonction triabulle().

Une autre façon de faire est d'indiquer d'abord l'existence des fonctions (prototypage) ce qui les rend alors connue. Ensuite, on peut alors les coder dans l'ordre que l'on veut. C'est d'ailleurs la seule façon de faire quand on a besoin d'une fonction a() qui va appeler b() alors que, dans le code de b(), on a un appel à a()...

Code c :

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
// Prototypage
int cmp(int, int);
void triabulle(...);    // Les "..." signifient que c'est incomplet et que tu dois toi-même trouver ce qui manque !!!
 
// Codage (l'ordre importe peu puisque le main() est lancé en premier)
void triabulle(...)
{
    ....
    ....
    ....
    if (cmp(t[i-1], t[i]) > 0)
    {
        // Interversion
        tmp=t[i-1];
        t[i-1]=t[i];
        t[i]=tmp;
    }
    ....
    ....
    ....
}
 
int cmp(int x, int y)
{
    if (x < y) return -1;
    if (x > y) return 1;
    return 0;
}

Invité · 08/11/2012, 19h20

Oui, je suis d'accord et j'ai procédé ainsi, voila pourquoi je trouvais étrange de devoir respecter un ordre si je les avais belle est bien déclarées avant... Merci.

Tri à bulles

C

Vue hybride

Discussions similaires

Partager

Partager