Discussion:Tri à bulles
- Admissibilité
- Neutralité
- Droit d'auteur
- Article de qualité
- Bon article
- Lumière sur
- À faire
- Archives
- Commons
Cet article est indexé par les projets Informatique et Mathématiques.
Les projets ont pour but d’enrichir le contenu de Wikipédia en aidant à la coordination du travail des contributeurs. Vous pouvez modifier directement cet article ou visiter les pages de projets pour prendre conseil ou consulter la liste des tâches et des objectifs.
| Avancement | Importance | pour le projet | |
|---|---|---|---|
| Bon début | Faible |  | Informatique (discussion • critères • liste • stats • hist. • comité • stats vues) |
 | Mathématiques (discussion • critères • liste • stats • hist. • comité • stats vues) | ||
Cet article ne comporte pas de liste de tâches suggérées. Vous pouvez saisir une liste de tâches à accomplir (par exemple sous forme d'une liste à puces), puis sauvegarder. Vous pouvez aussi consulter la page d'aide.
Erreur[modifier le code]
Partie implémentation : Dans le coeur de la boucle, il faut remplacer t[i] par t[j-1]. Dans l'état actuel des choses, cela ne fonctionne pas. Qlq peut-il me donner la confirmation ?
Effectivement. Corrigé. Il y a eu apparemment confusion avec le tri par insertion... FvdP (d) 25 mar 2005 à 18:42 (CET)
Confusion ?[modifier le code]
La version Pascal ne serait-elle pas elle aussi une version du tri par insertion (et non du tri à bulles ?)
lol — Le message qui précède, non signé, a été déposé par 82.67.77.42 (discuter), le 15 janvier 2007 à 00:21
Figure[modifier le code]
Il faudrait une explication plus claire de la figure. Si je comprends bien, pour chaque point, la valeur en x représente sa position dans la liste et la valeur en y représente sa valeur actuelle. Je préfère ne pas faire la modification moi-méme, n'étant pas certain de mon opinion. — Le message qui précède, non signé, a été déposé par Ban~frwiki (discuter), le 15 avril 2008 à 01:46
Implémentations[modifier le code]
Je trouve que la partie "Implémentations" est vraiment inutile. On va pas s'amuser à coder les exemples dans 10 langages différents. Le pseudo code est largement suffisant, après ce n'est qu'une histoire de syntaxe ! --Max81 (d) 19 octobre 2008 à 19:45 (CEST)
- J'approuve à 100%. Ce n'est pas le but de Wikipedia d'implémenter chaque algorithme dans chaque langage possible. À la rigueur, dans Wikibooks... Dans un article comme celui-ci, il devrait y avoir au plus UNE implémentation, soit en pseudo-code, soit dans un langage clairement lisible et de préférence le même pour tous les articles au moins d'un même sujet (ici le tri). FvdP (d) 12 janvier 2010 à 21:28 (CET)
Personnelement, la partie implementation C m'a servie. J'ai fait un copié collé et j'ai pu utilisé le code directement. Par contre, l'algo est faux (comme mentionné plus haut). C'est J et J-1 Je l'ai utilisé en le modifiant comme cela:
void tri_a_bulle(int *t, int const size)
{
bool en_desordre = true;
for (int i = 0; i < size && en_desordre; i++)
{
en_desordre = false;
for (int j = 0; j < size - i-1; j++)
if (t[j] > t[j + 1])
{
std::swap(t[j+1], t[j]);
en_desordre = true;
}
}
}
pseudo-code faux?[modifier le code]
En comparant avec la wiki allemande j'ai l'impression que le pseudo-code est faux, merci de vérifier.
Traduction du code de la wiki allemande, testé avec succès (en C):
procédure bubbleSort( A : liste des éléments)
n := longueur( A )
faire
échangé := faux
pour i de 1 à n - 1 faire
si A[ i ] > A[ i + 1 ] alors
échanger( A[ i ], A[ i + 1 ] )
échangé := vrai
fin si
fin pour
n := n - 1
tant que échangé et n > 1
fin procédure
- À part le fait que n est décrémenté à chaque étape (optimisation qui n'est pas essentielle), ça me semble strictement équivalent, non ? Nordald (d) 16 septembre 2010 à 23:41 (CEST)
Nombre d'échanges moyens pour un tableau rempli aléatoirement[modifier le code]
Il est dit dans la partie "Complexité" que lorsque l'ordre initial des éléments du tableau est aléatoire, le nombre d'échanges est en moyenne égal à n(n-1)/4. Ayant fait des tests de rapidité sur des tableaux avec n = 10000, il s'est avéré que le temps d'exécution de l'algorithme de tri à bulle était plus long que celui du tri par sélection. Or, le nombre d'échange effectué par le tri par sélection équivaut n(n+1)/2, il devrait donc être plus gourmand en temps d'exécution.
Merci de bien vouloir m'éclairer. (Le temps d'exécution du tri à bulle était en moyenne deux fois plus long)
- Même parmi les algorithmes de tri quadratique, le tri à bulle est réputé pour être le plus mauvais (je crois que Knuth donne une analyse détaillée dans TAOCP). Donc ces résultats expérimentaux sont normaux. Je pense que vous vous trompez sur l'aspect théorique : le tri par sélection ne fait que n échanges. Il fait un nombre quadratique de comparaisons, mais une implémentation standard reste plus efficace que le tri bulle. Nordald (d) 24 mars 2011 à 17:38 (CET)
Erreur Pseudo Code Non Optimisé ?[modifier le code]
Bonjour, je me suis appuyé sur ce pseudo-code pour faire programmer le tri à mes étudiants et il me semble qu'il y a une erreur dans le pseudo-code : i commence par prendre la valeur du dernier indice du tableau : n-1 en fin de deuxième boucle j a donc la valeur n-1 et j+1 est un indice en dehors du tableau --92.150.245.216 (discuter) 9 octobre 2015 à 17:49 (CEST)
- Dans ce pseudo-code, on ne lève pas l'exception t[n+1] mais l'idée est là. JackPotte ($♠) 9 octobre 2015 à 22:58 (CEST)
Erreur Pseudo Code Optimisé ?[modifier le code]
idem pour la version optimisé : pour j allant de 1 à i-1 pas 1 faire, le premier élément du tableau n'est pas trié puisque jamais examiné ! --92.150.245.216 (discuter) 9 octobre 2015 à 19:21 (CEST)
- Dans ce pseudo-code, le premier élément du tableau est t[1] (pas t[0]), il est donc comparé au début. JackPotte ($♠) 9 octobre 2015 à 22:55 (CEST)