Partage

Problème avec le tri à bulles

1 2 >>

Sujet résolu

7 juin 2007 à 20:21:02

Salut, je vais peut-être passer pour un vrai zér0 mais, après avoir lu plusieurs articles sur le tri à bulles, je pense comprendre le fonctionnement mais je ne vois pas comment l'utiliser. Comment faire, pour, par exemple, classer toutes les valeurs d'un tableau dans l'ordre croissant ? Si j'ai bien compris, il faut comparer le dernier élément et l'avant-dernier et si le dernier est plus petit, on inverse leur place ? Merci

GuilOooo

7 juin 2007 à 21:16:59

heu... Je ne sait pas comment tu fais, mais personnellement j'implémenterais ça comme ça :

SOIT x = 0

tant que x < longueur
-> Rechercher la plus petite valeur dans le tableau a partir de la case numéro X.
-> La permuter avec la case numéro X.
-> X++
fin

Ca doit être faisable en C, non ?
Sinon, postes ton début de code. On verra ce qu'il faut changer au fur et a mesure.

J'ai déménagé sur Zeste de savoir — Ex-manager des modérateurs.

anonymous

7 juin 2007 à 21:21:02

En fait, je voudrais que les valeurs que l'utilisateur rentre dans ce tableau soit classées par ordre croissant :

HanLee

7 juin 2007 à 21:22:08

GuilOooo : Non, c'est le tri par sélection ce que tu viens de faire.

Le principe du tri bulle, c'est de permuter 2 valeurs consécutives dans le tableau qui ne sont pas dans le bon ordre, jusqu'à ce qu'il n'y en ait plus.

GuilOooo

7 juin 2007 à 21:28:42

Citation

GuilOooo : Non, c'est le tri par sélection ce que tu viens de faire.

Ah ? au temps pour moi, désolé.

Citation

Le principe du tri bulle, c'est de permuter 2 valeurs consécutives dans le tableau qui ne sont pas dans le bon ordre, jusqu'à ce qu'il n'y en ait plus.

Mais ça paraît moins logique que le tri par sélection alors ? Bon bref.

Anonymous : ça c'est l'entrée, OK, mais après, tu as commencé un peu ? Genre tu parcours le tableau, a chaque fois si deux valeurs consécutives sont pas triées tu les permutes, et tu recommence jusqu'à ce que ça soit trié (faut sûrement faire un booléen pour savoir si tu as du faire une permutation ou pas pendant l'itération présente, si t'as pas eu à faire de permutations : la liste est triée, on stoppe).

J'ai déménagé sur Zeste de savoir — Ex-manager des modérateurs.

anonymous

7 juin 2007 à 21:32:11

C'est justement sur ce sujet que je ne vois pas comment faire.

GuilOooo

7 juin 2007 à 21:50:33

A quel moment exactement ?

Tu sais que tu vas avoir une boucle qui va se continuer tant que notre flag est à true. Donc déjà on a un bool et une boucle. Et, a chaque tour, on remet le flag à false.

Ensuite, il faut parcourir le tableau : une deuxième boucle imbriquée. Et, à chaque itération, on fait quoi ? On compare la case testée avec la valeur suivante, si elles sont pas dans l'ordre, on permute, on mets le flag à true.

Et normalement ça devrait aller (je peux me tromper). A quel moment précis tu bloques dans ces étapes ?

J'ai déménagé sur Zeste de savoir — Ex-manager des modérateurs.

anonymous

7 juin 2007 à 22:06:43

int tailleTableau,tem,a,b;
cout<<"Tapez le nombre de nombres que vous voulez classer dans l'ordre croissant :"<<endl;
cin>>tailleTableau;
long tab[tailleTableau];
while (i<tailleTableau)
{
i++;
cout << "Valeur numéro " << i << " :" << endl;
cin >> x;
tab[i] = x;//On remplit la case correspondante
}
for (a=0; a<tailleTableau-1,a++;)
{
for (b=0; b<tailleTableau-1, b++;)
{
if (tab[b+1] < tab[b])
{

tem= tab[b+1];
tab[b+1] = tab[b];
tab[b] = tem;
}
}
}
cout<<tab[b]<<endl;

J'ai essayé avec cet algorithme et cela me renvoie :

Segmentation fault (core dumped)

GuilOooo

7 juin 2007 à 23:12:43

Heu.. La je vois pas.
Ben déjà on commence, maintenant reste plus qu'a rajouter un booléen que tu mets à true si tu rentres dans le if(tab[b+1] < tab[1]), et englober le tout avec une boucle, non ?

Sinon, pour la seg fault, désolé mais là je verrais ça demain.

J'ai déménagé sur Zeste de savoir — Ex-manager des modérateurs.

seb2003

8 juin 2007 à 0:29:55

bon, imagine ton tableau de N éléments
tu fais une boucle avec comme gardien:

while(N > 1){
// ici on va faire en sorte que la fin du vecteur soit trié
// puis on decrémente N
}

Pour l'intérieur de la boucle tu fais une deuxieme qui amène la plus grande valeur du vecteur [0..N-1] en position N-1

a = 1;
while(a < N){
if(V[a]<V[a-1]){
switch(V[a], V[a-1])
}
a++;
}

je fais ca de memoire, je verifie quand j'ai le temps..

Anonyme

8 juin 2007 à 7:46:20

Pour le segfault, c'est simplement parce que tu incrémentes i au début de la boucle. Donc i ira de 1 à tailleTableau et pas de 0 à tailleTableau-1.
Sinon, le tri à bulles, en fait, à un algorithme similaire à ca:

SOIT x=1

TANT QUE x < tailleTableau-1
-> SOIT y=0
-> TANT QUE y < tailleTableau-x
-> -> Si la case y du tableau est plus grande que la case y+1, les inverser
-> -> y++
-> x++

Il est basé sur le fait qu'à chaque tour de la boucle interne, le plus grand élément du tableau se retrouve dans tous les cas en fin de tableau. D'où le nom de tri à bulles: tel une bulle remontant à la surface, le plus grand nombre se range en bout de tableau.

anonymous

8 juin 2007 à 14:40:23

J'ai ce bout de code mais, je ne sais pas s'il est bon :

for (int a=0; a<tailleTableau-1, a++;)
{
for (int b=0;b<tailleTableau-a, b++;)
{
if (b+1<b)
{
rev=tab[b+1];
tab[b+1]=tab[b];
tab[b]=rev;
a++;
b++;
}

}

}

Nanoc

8 juin 2007 à 19:29:25

J'aurai fait un truc du genre:

bool fin(false); //On est pas deja a la fin de l'algorithme ;-)
float temp;
do{ //Tant qu'il reste des éléments a echanger
fin = true; //Si on ne fait aucun echange l'algorithme se termine
for(unsigned int i(1); i < taille;++i) //On parcourt le tableau
{
if(tableau[i] < tableau[i-1]) //Si un nombre est plus petit que le precedent
{
temp = tab[i];
tab[i] = tab[i-1]; //On procede a l'echange
tab[i-1] = temp;
fin = false; //On devra refaire un test
}
}
}while(!fin); //Tant qu'il reste des éléments mal places

Il est à noter que c'est algorithme est particulièrement inefficace mais facile à coder.

Co-auteur du cours de C++. ||| Posez vos questions sur le forum ||| Me contacter.

MatteX

8 juin 2007 à 19:30:22

penses-y !

on a un tableau contenant 5 valeurs dans l'ordre :

0	1	2	3	4
5	2	4	3	1

on fait un test avec ton algorithme (

for (int a=0; a<tailleTableau-1, a++;)
{
for (int b=0;b<tailleTableau-a, b++;)
{
if (b+1<b)
{
rev=tab[b+1];
tab[b+1]=tab[b];
tab[b]=rev;
a++;
b++;
}
}
}

tour boucle a
a = 0;

tour boucle b
b = 0;

b + 1 < b ( 0+1 < 0 ) faux!

tour boucle b
b = 1;

b + 1 < b ( 1+1 < 1 ) faux!

tour boucle b
b = 2;

b + 1 < b ( 2+1 < 2 ) faux!

est-ce que j'ai touché au tableau? ;-) prend mon tableau de test et écrit chaque étape de ce que tu veux faire, et ensuite pense à ton algorithme sur papier. écrit les valeurs de tes variables et de ton tableau.

Bonne chance

EDIT : Nanoc! Un si beau problème permettant la compréhension d'un Zér0 et tu lui donne la réponse!

anonymous

8 juin 2007 à 21:56:28

Non, désolé mais je ne vois vraiment pas comment faire un algorithme de tri à bulles qui marche.

Nanoc

8 juin 2007 à 22:22:05

Citation : anonymous

Non, désolé mais je ne vois vraiment pas comment faire un algorithme de tri à bulles qui marche.

Mais LOL, regarde les posts...

Citation : Mattex

EDIT : Nanoc! Un si beau problème permettant la compréhension d'un Zér0 et tu lui donne la réponse!

T as raison je m'abstiendrai la prochaine fois.

Co-auteur du cours de C++. ||| Posez vos questions sur le forum ||| Me contacter.

anonymous

8 juin 2007 à 23:22:31

Oui, mais justement, je ne vois pas en quoi mes algorithmes sont faux !

seb2003

9 juin 2007 à 0:02:13

deja tu compare des indice, et pas les valeurs de ton tableau..

anonymous

9 juin 2007 à 9:30:53

for (a=0; a<tailleTableau-1, a++;)
{
for (b=0; b<tailleTableau-a, b++;)
{
if (tab[i]<tab[i-1])
{
temp = tab[i];
tab[i] = tab[i-1]; //On procede a l'echange
tab[i-1] = temp;
}}}
cout<<temp<<endl;

Mais dans ce code-ci, je compare les valeurs des tableaux et cela ne marche pas.

seb2003

9 juin 2007 à 10:50:59

il vient d'ou ton i?? tu declare que des a et b...

anonymous

9 juin 2007 à 11:49:38

int tailleTableau;
cout<<"Tapez le nombre de nombres que vous voulez classer dans l'ordre croissant :"<<endl;
cin>>tailleTableau;
long tab[tailleTableau];
while (i<tailleTableau)
{
i++;
cout << "Valeur numéro " << i << " :" << endl;
cin >> x;
tab[i] = x;//On remplit la case correspondante
}
for (a=0; a<tailleTableau-1, a++;)
{
for (b=0; b<tailleTableau-a, b++;)
{
if (tab[i]<tab[i-1])
{
temp = tab[i];
tab[i] = tab[i-1]; //On procede a l'echange
tab[i-1] = temp;
}}}
cout<<temp<<endl;

J'avais oublié cette partie du code.

seb2003

9 juin 2007 à 11:51:42

tu ne declare toujours pas i, et n'oublie pas de le réinitialiser à 0 avant ta boucle for

anonymous

9 juin 2007 à 13:05:29

long i=0;
int tailleTableau;
cout<<"Tapez le nombre de nombres que vous voulez classer dans l'ordre croissant :"<<endl;
cin>>tailleTableau;
long tab[tailleTableau];
while (i<tailleTableau)
{
i++;
cout << "Valeur numéro " << i << " :" << endl;
cin >> x;
tab[i] = x;//On remplit la case correspondante
}
int i=0;
for (a=0; a<tailleTableau-1, a++;)
{
for (b=0; b<tailleTableau-a, b++;)
{
if (tab[i]<tab[i-1])
{
temp = tab[i];
tab[i] = tab[i-1]; //On procede a l'echange
tab[i-1] = temp;
}}}
cout<<temp<<endl;
}

Comme ça ? Mais ce code ne marche pas.

Anonyme

9 juin 2007 à 13:30:01

Dans tes 2 boucles imbriquées, ça sert à quoi que tu compares tab[i] et tab[i-1] alors que c'est a et b qui varient ?

anonymous

9 juin 2007 à 13:39:40

Donc, concrètement, je devrais comparer a et b ? Mais comment ?

Anonyme

9 juin 2007 à 15:18:41

salut,

1. il y a encore un autre problème : dans la boucle ou tu remplit le tableau, tu incrémente i au début de la boucle : il faut le faire à la fin.
2. Ensuite, au début, tu déclare long i=0, et plus loin int i=0. Faut choisir : soit long, soit int !
3. Tu utilises des a et des b mais sans les déclarer !

Une petite optimisation, quand tu met la valeur dans le tableau, t'a pas besoin de variable intermédiaire, tu fait : cin>>tab[i];

Ensuite, je voit pas ce que tu fait avec tes 2 boucles for.
Je vais te donner une méthode :
tant qu'on fait des échanges, on continue à parcourir le tableau et à echanger si besoin est. Il y a donc deux boucles : 1 while avec le booléen des échanges et un for qui parcours le tableau et dans ce for, un if qui vérifie les valeurs et les échange si besoin est. dans ce if, le booleen est mit à vrai. Avant le début du if, le booléen est mit a faut dans le cas ou il n'y a plus de permutation, ce qui veut dire que le tableau est trié.

Avec ces indications, tu devrait y arriver !

Xav57

anonymous

9 juin 2007 à 19:18:34

int tailleTableau, temp;
bool verif (false);
cout<<"Tapez le nombre de nombres que vous voulez classer dans l'ordre croissant :"<<endl;
cin>>tailleTableau;
long tab[tailleTableau];
while (i<tailleTableau)
{
i++;
cout << "Valeur numéro " << i << " :" << endl;
cin >> x;
tab[i] = x;//On remplit la case correspondante
}//algorithme de tri à bulles
while (verif!=true)
{
for (unsigned int i(1); i < tailleTableau;++i)
{
if(tab[i]<tab[i-1])
{
temp = tab[i];
tab[i] = tab[i-1]; //On procede a l'echange
tab[i-1] = temp;
verif = false;
}
}
}
cout<<tab[i];

J'ai codé ça mais on dirait qu'il y a une boucle infinie quelque part et je ne vois pas où.

Anonyme

9 juin 2007 à 19:40:16

tu peut donner le code complet parce que chez, ça compile pas !
Mais d'après ce que je voit, tu y es presque !
y'a quand meme une erreur de logique avec ton booléen -> tu le met à faux, tant que qu'il est à faux, on continue la boucle, si on fait un échange, on le met à faux, bref, il ne passe jamais à vrai, donc la boucle ne se termine pas => elle est là ta boucle infinie !

anonymous

9 juin 2007 à 20:01:17

C'est bon, j'ai corrigé le problème des booléens mais je ne sais pas quoi afficher pour voir le tableau trié dans l'ordre croissant.

Anonyme

9 juin 2007 à 20:11:47

Pour afficher le tableau : une boucle qui boucle dans que le compteur n'a pas atteint le dernier élément.
Secret (cliquez pour afficher)

for(int j = 0; j<taille_tableau; j++)
{
cout<<tab[j]<<endl;
}

1 2 >>