PETIT ALGO DE TRI...

cs_dominion Messages postés 230 Date d'inscription mardi 21 janvier 2003 Statut Membre Dernière intervention 15 mai 2008 - 17 févr. 2005 à 17:15
cs_dominion Messages postés 230 Date d'inscription mardi 21 janvier 2003 Statut Membre Dernière intervention 15 mai 2008 - 20 févr. 2005 à 23:36

Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.

https://codes-sources.commentcamarche.net/source/29541-petit-algo-de-tri

cs_dominion Messages postés 230 Date d'inscription mardi 21 janvier 2003 Statut Membre Dernière intervention 15 mai 2008
20 févr. 2005 à 23:36

Voilà pour le Merge Sort :
http://www.cppfrance.com/code.aspx?ID=29675

cs_dominion Messages postés 230 Date d'inscription mardi 21 janvier 2003 Statut Membre Dernière intervention 15 mai 2008
19 févr. 2005 à 14:44

Tu peux aussi mettre un compteur de temps, mais c'est très bourrin : l'utilisation des autres proggs fausse le calcul et ca change très fort pour les longs algo (j'ai déjà eu 1 seconde d'écart pour un algo de 30 sec exécuté 2 fois !!!)

cs_Kirua Messages postés 3006 Date d'inscription dimanche 14 avril 2002 Statut Membre Dernière intervention 31 décembre 2008
19 févr. 2005 à 13:27

C'est exacte pmbala, la comparaison de deux programmes est un problème incalculable (ce qui se traduit par l'impossibilité absolue d'écrire un programme qui teste l'équivalence entre deux programmes donnés). Mais ce que je te propose, c'est de, à la main, analyser ton propre code pour en retirer une idée de l'évolution de la quantité de ressources (temps / mémoire) qui seront nécessaire à ton algo à mesure qu'on lui demandera de traîter un problème plus gros. Ça te permet (mais ce n'est pas le but premier) d'estimer combien de temps ton algo mettra à trier une liste de 1 000 000 d'éléments si tu sais en combien de temps il trie une liste de 10 000 éléments. Mais comme je te disais, ça sert plus à comparer les algos entre eux qu'à faire des prévisions, parce que le calcul de complexité est très grossier et imprécis.

cs_dominion Messages postés 230 Date d'inscription mardi 21 janvier 2003 Statut Membre Dernière intervention 15 mai 2008
18 févr. 2005 à 17:27

En fait, tu peux calculer la complexité en ragardant combien de fois ton code effectuera le contenu des boucles. Dans ton cas n², si j'ai bien lu...
Si tu veux en savoir plus, je ne peux que trop te conseiller l'excellent article de Kirua justement (que je remercie) :
http://www.coder-studio.com/?page=tutoriaux_aff&code=autre_3

Je viends d'écrire un algo de type Merge Sort (de complexité O(n logn/log2)) en pseudo code... Le temps de l'écrire en C++ et je l'envoie sur le site.

pmbala Messages postés 30 Date d'inscription samedi 4 décembre 2004 Statut Membre Dernière intervention 2 avril 2008
18 févr. 2005 à 11:55

Oui dominion, je sais que mon truc sur le tri est tres tres lent,et c'est pr cela que j'ai tenu à preciser que c'etait pour les debutants de chez debutants,ravi de savoir que tu pourras l'utiliser à de meilleures fins...(fais nous savoir la suite)

Kirua , je me suis aussi demandé comment faire pr comparer des algos,mais j'avais un prof qui m'avait dit qu'il n'existait pas d'algo capable de faire la comparaison de deux algos...bon je crois avoir mal lu ce que tu voulais dire,je vais aller voir ces tutos pour en savoir plus... merci à tous

cs_Kirua Messages postés 3006 Date d'inscription dimanche 14 avril 2002 Statut Membre Dernière intervention 31 décembre 2008
17 févr. 2005 à 22:24

Je rajouterais que si l'algorithmique vous intéresse et si vous désirez savoir comment comparer deux algos, une solution est d'apprendre à calculer la complexité d'un algorithme (c'est simple, faites une petite recherche sur google sur "calcul complexité algorithme" et vous trouverez des tutos. Ce que ça permet en gros: évaluer les performances d'un algo par rapport à un autre à mesure qu'on lui demande de traiter des cas plus compliqués (ici par exemple, trier des plus gros tableaux)

cs_dominion Messages postés 230 Date d'inscription mardi 21 janvier 2003 Statut Membre Dernière intervention 15 mai 2008
17 févr. 2005 à 17:15

Merci pour ton code, et surtout bravo pour avoir fait savoir qu'il était mauvais (si si), du moins du côté de sa vitesse... Pour les débutants c'est vrai que c'est très intéressant. Je suis actuellemnt en train d'étudier différents algo de tri, donc merci pour ton code, je ne connaissait pas celui-là...

Pour ceux que le tri intéresse : http://en.wikipedia.org/wiki/Sorting_algorithm (en anglais)

Discussions similaires

Algo championnat de foot

Fonction de TRI -

tri par base ou radix

algorithme de tri par base en c

Tri Radix (Tri par base)

Votre réponse

Discussions similaires