Complexité des Tri

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!

Bonsoir,
J'ai lu bcp mais j'ai pus y répondre
Peux tu me faciliter les choses?
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!

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

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.

Bonsoir,
J'ai trouvé n(n-1)/2 dans les documents en googling mais le nombre de permutations ??? je ne sais pas
Merci