Problème avec le tri à bulles

<< 1 2

Sujet résolu

9 juin 2007 à 21:51:15

J'ai compris mais je ne vois pas comment l'appliquer ici :

int tailleTableau,temp;
long i=0;
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=false)
{
for (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 = true;

}}
}

Anonyme

9 juin 2007 à 22:19:38

ben tu met la boucle après la boucle qui fait l'échange, donc après la fin de la deuxième boucle while.

Ensuite, pour le tri, c'est pas encore bon !

1. pour vérifier l'état du booléen, ce n'est pas while(verif = false) mais while(verif == false) (il y a 2 =)
2. dans la première boucle while, il faut mettre le ++i après avoir mit la valeur dans le tableau
3. la boucle for, il faut la faire commencer à 0 et pas a un car dans un tableau, la première à le numéro 0 et pas 1
4. tu déclare verif = false, ta boucle while avec while(verif == false) et dès que tu fait le premier échange, quand la boucle for sera arrivé a la fin du tableau, on ne rentrera plus dans le tableau : cette boucle doit etre faite dans qu'on fait des permutations
5. dans ton if, tu verifie une valeur avec celle d'avant : c'est pas plutot l'inverse ??

anonymous

9 juin 2007 à 22:50:35

J'ai adapté mon algorithme à ce que tu m'as dit mais il ne marche toujours pas correctement :

int i =1;
int tailleTableau;
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)
{
cout << "Valeur numéro " << i << " :" << endl;
cin >> x;
tab[i] = x;//On remplit la case correspondante
i++;
}//algorithme de tri à bulles
while (verif==false)
{
for (int i=0; i < tailleTableau;++i)
{
if(tab[i]>tab[i-1])
{
tab[i]=temp;
tab[i-1]=tab[i]; //On procede a l'echange
temp=tab[i-1];
verif = true;

}}
}
cout<<"Les valeurs classées dans l'ordre croissant sont :"<<endl;
for(int j = 0; j<tailleTableau;)
{
cout<<tab[j]<<endl;
j++;
}

Anonyme

9 juin 2007 à 23:04:24

Bien, t'a modifié certaines partie en mieu et d'autre en pire !!

1. Pour remplir le tableau, la première case est un ZERO, donc ton i doit etre égal a 0 et pas a 1
2. t'a boucle for pour afficher le tableau est mal construite : c'est for(int j=0; j<tailleTableau; j++) => il ne faut pas séparer le j++ du reste . C'est bizarre, dans ta première boucle for, tu le fait bien, mais pas dans la deuxième !!
3. dans le if, tu a modifié des trucs, mais c'est encore pire qu'avant : tu fait : tab[i] = temp =>
a) temp n'est pas déclaré
b) c'a na aucun sens, bien que je voit ce que tu veut faire. Prend une feuille et déroule ton if : tu comprendra ce qui ne va pas
4. Le point 5 de mon précédent post reste valable

anonymous

9 juin 2007 à 23:20:39

Désolé mais je ne vois vraiment pas comment faire pour l'échange des variables dans le if.

MatteX

11 juin 2007 à 19:47:59

Ok mon grand!

Tu ne veux pas comprendre nos simples explications, je vais donc te recaler. Voici les trois chapitre nécessaire à la compréhension des variables, des conditions et des boucles. Car si tu n'est pas capable de mettre en code le tri a bulle avec toute nos explications c'est que tu n'as pas compris quelque chose.

http://www.siteduzero.com/tuto-3-1224-1-un-monde-de-variables.html
http://www.siteduzero.com/tuto-3-2192-1-les-conditions.html
http://www.siteduzero.com/tuto-3-2478-1-les-boucles.html

Ce n'est pas méchant mais nécessaire, Je crois que le que ta plus grande difficulté c'est les boucles. Pioche, relis et essaye d'imaginer comment tu peux utiliser ces outils dans le but de parcourir un tableau et de replacer les éléments (nombres) qu'il contient dans l'ordre que tu veux.

Comment tu peux afficher le contenu d'un tableau...

tout y est

anonymous

11 juin 2007 à 21:53:48

Ecoute : je connais le C depuis presque 1 an et demi (je débute en C++) mais, le problème, c'est que je n'ai pas suivi un seul tutoriel bien précis mais plusieurs tutoriels en parallèles (avec chacun des méthodes différentes) avec quelques exemples de codes sources. Donc, je reconnais que j'ai quelques lacunes au niveau des tableaux.

MatteX

12 juin 2007 à 15:18:22

Alors dis-moi qu'est-ce qu'un tableau dans tes mots?

anonymous

12 juin 2007 à 16:15:36

Je dirais qu'un tableau est une sorte de "super variable" qui peut stocker les valeurs de plusieurs variables.
Désolé pour le coup de gueule.

MatteX

12 juin 2007 à 17:59:54

Si je te pose cette question c'est que j'essaye de t'aider le mieux possible pour que tu comprenne le fonctionnement du tri à bulles. Certes tu peux ne pas répondre mais tu peux aussi ne pas avoir d'aide.

Ta réponses est bonne mais incomplète : Un tableau c'est une suite contigüe d'espaces mémoires de même longueur. la longueur de chaque espace est défini selon le type du tableau : un tableau de taille 3 et de type int réservera 3 fois la taille d'un int en mémoire.

<-----TAILLE------>
+-----+-----+-----+
| int | int | int |
+-----+-----+-----+

la variable contenant l'adresse du tableau contient en fait une référence sur la première "case mémoire" du tableau

là
|
+-----+-----+-----+
| int | int | int |
+-----+-----+-----+

lorsque j'utilise l'opérateur [] je déplace le "pointeur" du nombre de case indiqué dans entre les crochet

Ex. tab[ 1 ] = (adresse de tab) + 1 * (taille de int)

ici
|
+-----+-----+-----+
| int | int | int |
+-----+-----+-----+

donc on voit que pour un tableau d'une taille de 3 cases on ne peut que lire de 0 à 2

0---->1---->2---->3->déborde
| | |
+-----+-----+-----+
| int | int | int |
+-----+-----+-----+

Alors mettons tout ça en pratique :

Si je veux dans une boucle faire le tour de chacune des cases je peux utiliser une variable et passer de 0 à 2 en faisant un pas de 1 à chaque tour

// exemble d'affichage de toute les valeurs d'un tableau
for( int i = 0; i < taille_tableau; i++ )
{
cout << "valeur case " << i << " = " << tab[ i ] << endl;
}

je peux facilement mettre tout ça dans une fonction... c'est la même chose pour le tri à bulles.

Comme te l'on dit plusieurs, voici son fonctionnement :

Outils :
1) un flag (booléen) pour vérifier les changements à chaque passage
2) une variable du même type que le tableau pour l'échange.

Recette :
1) Ont commence par lire tout le tableau (personnellement je préfère le lire à l'envers) et on vérifie que notre case est bien ordonnée avec sa voisine.

Si elles ne sont pas dans le bon ordre on les échanges et on change notre booléen qui vérifie s'il y a eu au moins 1 changement dans la lecture complète du tableau

Lorsqu'on a vérifié tout le tableau (chaque case avec sa voisine supérieur OU inférieur) et qu'il y a eu au moins un changement, on réinitialise notre booléen à pas de changement et on recommence la lecture du tableau et ce jusqu'à ce qu'il n'y ai AUCUN changement dans un passage complet.

Notre tableau est donc trié s'il n'y a aucun passage (logiquement)

le prochain tableau fait un exemple avec toute les opérations

Case 0	Case 1	Case 2	Description de l'action
2	12	1	Tableau de départ
2	12	1	validation case 0 < case 1 = VRAI alors ont fait rien
2	12	1	validation case 1 < case 2 = FAUX alors échange
2	1	12	échange case 1 avec case 2
2	1	12	Fin de lecture du tableau, il y a eu échange ont recommence
2	1	12	validation case 0 < case 1 = FAUX alors échange
1	2	12	échange case 0 avec case 1
1	2	12	validation case 1 < case 2 = VRAI
1	2	12	Fin de lecture du tableau, il y a eu échange ont recommence
1	2	12	validation case 0 < case 1 = VRAI
1	2	12	validation case 1 < case 2 = VRAI
1	2	12	Fin de lecture, aucun échange donc fin de tri

Maintenant à ton tour de coder quelque chose qui fait exactement ça, tu as les outils, fait attention à ne pas perdre de données et à ne pas déborder de ton tableau en le lisant.

Petit truc : tu peux afficher les cases de ton tableau avant et après le tri pour vérifier ton code, tu peux aussi afficher ton tableau à chaque tour de boucle pour vérifier chacun de tes échanges.

anonymous

12 juin 2007 à 20:00:48

C'est bon, j'ai réussi à créer un algorithme de tri à bulles qui classe les nombres dans l'ordre croissant et décroissant. Merci

HanLee

12 juin 2007 à 20:30:42

Je peux voir le code ?

Je pense que j'aurais peut-être un commentaire à faire dessus.

anonymous

12 juin 2007 à 21:19:37

Bien sur :

int tailleTableau;
long i=0;
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)
{
cout << "Valeur numéro " << compteur << " :" << endl;
cin >> x;
tab[i] = x;//On remplit la case correspondante
i++;
compteur++;
}//algorithme de tri à bulles
while (verif==false)
{
verif = true;
for (int i=0; i<tailleTableau-1;++i)
{
if(tab[i]>tab[i+1])
{
temp=tab[i];
tab[i]=tab[i+1];
tab[i+1]=temp;

verif=false;
}}}
cout<<"Les valeurs classées dans l'ordre croissant sont :"<<endl;
for(int j=0; j<tailleTableau;++j)
{
cout<<tab[j]<<endl;
}

MatteX

12 juin 2007 à 21:45:12

Est-ce que ce que je t'ai dit t'as été utile? Ou tu as trouvé ailleurs?

petite chose :

while( verif == false )
// S'écrit facilement
while( !verif )

Ce n'est pas très grave mais pourquoi faire une opération de comparaison sur un booléen?

anonymous

12 juin 2007 à 21:52:43

Pour pouvoir stopper la boucle while après le tri.

MatteX

12 juin 2007 à 22:21:29

C'est que je te dis

while( verif == false )

C'est la même chose que

while( !verif )

Seulement un petit commentaire, c'est plus accepté sous cette forme

<< 1 2