Complexité des Tri
YannicBesquent
Messages postés
9
Statut
Membre
-
YannicBesquent Messages postés 9 Statut Membre -
YannicBesquent Messages postés 9 Statut Membre -
Salut,
J'ai 2 questions sur la complexité des tri que j'ai pas pu trouvé de solution pour eux:
2)Dans le pire des cas ,le tri à bulle d'un tableau à n éléments fait :
*n(n-1) permutations
*n^2 comparaisons
*n! permutations
2)Dans le meilleur des cas, le tri par sélection d'un tableau à n éléments fait
*n comparaisons
*0 permutation
*n(n-1)/2 comparaisons
Merci bien pour votre collaboration
J'ai 2 questions sur la complexité des tri que j'ai pas pu trouvé de solution pour eux:
2)Dans le pire des cas ,le tri à bulle d'un tableau à n éléments fait :
*n(n-1) permutations
*n^2 comparaisons
*n! permutations
2)Dans le meilleur des cas, le tri par sélection d'un tableau à n éléments fait
*n comparaisons
*0 permutation
*n(n-1)/2 comparaisons
Merci bien pour votre collaboration
A voir également:
- Complexité des Tri
- Comment faire un tri personnalisé sur excel - Guide
- Logiciel tri photo - Guide
- Tri turf - Télécharger - Sport
- Wap tri - Télécharger - Divers TV & Vidéo
- En cours de traitement sur le site de tri local ✓ - Forum Consommation & Internet
6 réponses
Un peu de lecture. Les solutions s'y trouvent.
Tri à bulles: https://fr.wikipedia.org/wiki/Tri_%C3%A0_bulles
Tri par sélection: https://fr.wikipedia.org/wiki/Tri_par_s%C3%A9lection
Je pourrais te donner les solutions ici mais ce serait trop facile! ;)
Bonne chance!
Tri à bulles: https://fr.wikipedia.org/wiki/Tri_%C3%A0_bulles
Tri par sélection: https://fr.wikipedia.org/wiki/Tri_par_s%C3%A9lection
Je pourrais te donner les solutions ici mais ce serait trop facile! ;)
Bonne chance!
La première chose que tu dois remarquer est la différence entre permutation et comparaison dans les questions.
Indice (ou réponse) pour la question 2:
Quand on parle du meilleur cas dans un situation de tri, on parle d'une liste déjà triée. Avec le tri par sélection, si la liste est déjà triée, aucun élément n'est déplacé, autrement dit, aucun élément n'est permuté. Pour les comparaisons, le tri par sélection en effectue toujours le même nombre, dans tous les cas et ce nombre est n(n-1)/2 comme mentionné dans la page wikipedia ci-haut dans la section Complexité.
Je vais te laisser réfléchir un peu plus pour la question 1.
Bonne chance!
Indice (ou réponse) pour la question 2:
Quand on parle du meilleur cas dans un situation de tri, on parle d'une liste déjà triée. Avec le tri par sélection, si la liste est déjà triée, aucun élément n'est déplacé, autrement dit, aucun élément n'est permuté. Pour les comparaisons, le tri par sélection en effectue toujours le même nombre, dans tous les cas et ce nombre est n(n-1)/2 comme mentionné dans la page wikipedia ci-haut dans la section Complexité.
Je vais te laisser réfléchir un peu plus pour la question 1.
Bonne chance!
Bonsoir,
Oui pour la question 2) cava
Pour le 1) dans le pire des cas(t&bleau trié dans l'ordre inverse),le tri à bulles fait n(n_1)/2 comparaisons mais le nombre de permutation j'ai pas pu le calculer
Merci pour votre aide
Oui pour la question 2) cava
Pour le 1) dans le pire des cas(t&bleau trié dans l'ordre inverse),le tri à bulles fait n(n_1)/2 comparaisons mais le nombre de permutation j'ai pas pu le calculer
Merci pour votre aide
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question