Complexité des Tri [Fermé]

Messages postés
6
Date d'inscription
mercredi 8 décembre 2010
Statut
Membre
Dernière intervention
9 décembre 2010
- - Dernière réponse : YannicBesquent
Messages postés
6
Date d'inscription
mercredi 8 décembre 2010
Statut
Membre
Dernière intervention
9 décembre 2010
- 9 déc. 2010 à 20:58
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
Afficher la suite 

6 réponses

Messages postés
630
Date d'inscription
mardi 12 juin 2007
Statut
Membre
Dernière intervention
19 février 2016
372
0
Merci
Un peu de lecture. Les solutions s'y trouvent.

Tri à bulles: http://fr.wikipedia.org/wiki/Tri_%C3%A0_bulles
Tri par sélection: http://fr.wikipedia.org/wiki/Tri_par_s%C3%A9lection

Je pourrais te donner les solutions ici mais ce serait trop facile! ;)

Bonne chance!
Messages postés
6
Date d'inscription
mercredi 8 décembre 2010
Statut
Membre
Dernière intervention
9 décembre 2010
0
Merci
Bonsoir,
J'ai lu bcp mais j'ai pus y répondre
Peux tu me faciliter les choses?
Merci
Messages postés
630
Date d'inscription
mardi 12 juin 2007
Statut
Membre
Dernière intervention
19 février 2016
372
0
Merci
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!
Messages postés
6
Date d'inscription
mercredi 8 décembre 2010
Statut
Membre
Dernière intervention
9 décembre 2010
0
Merci
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
Messages postés
630
Date d'inscription
mardi 12 juin 2007
Statut
Membre
Dernière intervention
19 février 2016
372
0
Merci
Es-tu certains du nombre de comparaisons?

Selon moi, il s'agirait plutôt du nombre de permutations.

Tri à bulles:
Comparaisons: n(n-1)
Permutations: n(n-1)/2

Par exemple:
Si j'applique le tri à bulle sur la liste 4,3,2,1
Je dois faire 12 comparaisons et 6 permutations.
Messages postés
6
Date d'inscription
mercredi 8 décembre 2010
Statut
Membre
Dernière intervention
9 décembre 2010
0
Merci
Bonsoir,
J'ai trouvé n(n-1)/2 dans les documents en googling mais le nombre de permutations ??? je ne sais pas
Merci