Complexité des Tri
Fermé
YannicBesquent
Messages postés
6
Date d'inscription
mercredi 8 décembre 2010
Statut
Membre
Dernière intervention
9 décembre 2010
-
8 déc. 2010 à 21:13
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
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
A voir également:
- Complexité des Tri
- Tri excel - Guide
- Logiciel de tri de photos - Guide
- Triez ce tableau par ordre alphabétique des prénoms - Forum LibreOffice / OpenOffice
- Triez cette liste par ordre alphabétique des villes et par note de la meilleure à la moins bonne. quel mot est formé par les 8 premières lettres de la colonne code ? ✓ - Forum Excel
- Excel tri par date ne fonctionne pas ✓ - Forum Excel
6 réponses
Doctor C
Messages postés
627
Date d'inscription
mardi 12 juin 2007
Statut
Membre
Dernière intervention
19 février 2016
398
8 déc. 2010 à 22:32
8 déc. 2010 à 22:32
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!
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 à 00:52
9 déc. 2010 à 00:52
Bonsoir,
J'ai lu bcp mais j'ai pus y répondre
Peux tu me faciliter les choses?
Merci
J'ai lu bcp mais j'ai pus y répondre
Peux tu me faciliter les choses?
Merci
Doctor C
Messages postés
627
Date d'inscription
mardi 12 juin 2007
Statut
Membre
Dernière intervention
19 février 2016
398
9 déc. 2010 à 15:54
9 déc. 2010 à 15:54
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!
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 à 17:03
9 déc. 2010 à 17:03
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
Doctor C
Messages postés
627
Date d'inscription
mardi 12 juin 2007
Statut
Membre
Dernière intervention
19 février 2016
398
9 déc. 2010 à 19:35
9 déc. 2010 à 19:35
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.
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.
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
9 déc. 2010 à 20:58
Bonsoir,
J'ai trouvé n(n-1)/2 dans les documents en googling mais le nombre de permutations ??? je ne sais pas
Merci
J'ai trouvé n(n-1)/2 dans les documents en googling mais le nombre de permutations ??? je ne sais pas
Merci
