algorithme de tri

[invite8f81fa85]

bonsoir ,je ne sais pas si ce message est bien a sa place ,..mais bon ........
j'ai des algorithmes de tri (bubble ,ripple ...etc) en tout j'en ai cinq ,et il faut que je les comparent .
voici mes problemes
-tout d'abord je ne sais pas comment utiliser la fonction random pour remplire les different tableaux(ca ve pas ché-mar)
-ensuite,il faut que j'accede à l'horloge systeme pour chronometrer le temp d'éxécution de chaque methode (j'ai pensé a clock),mais ca aussi ca me pose problème
-dernier problème,et pas des moindres,je dois ecrire une fonction qui dessine le graphique de l'execution de chaque méthode et la,je ne sais meme pas par ou commencer.

toute aide est bienvenue
merci d'avance
-----

[Coincoin]

Salut,
La moindre des choses serait de préciser le langage, non ?

[invite7a8ce750]

Que tu les compares dans quel sens ?
Si c'est de calculer leurs complexités, cela se fait sans les implémenter.

[Brikkhe]

En terme de rapidité et d'efficassité peut être...

[A voir en vidéo sur Futura]

[invite6de5f0ac]

Bonjour,

L'analyse d'un algorithme (ceux de tri sont des cas particulièrement simples) peut se faire indépendamment du langage. Ce n'est pas toujours facile mais c'est faisable.

Maintenant s'il s'agit de mesurer effectivement leur vitesse et leur efficacité, il faut préciser le langage et le processeur. Un P5 sait (avec un bon compilo) paralléliser jusqu'à 4 opérations (c'est utilisé dans au moins un compilo FORTRAN 99), ça change nettement les performances. Et accessoirement, j'aimerais bien pouvoir écrire en C++ quelque chose comme "a >< b" pour dire "échanger a et b" sans avoir besoin d'une variable intermédiaire (au fait, pour des entiers: essaye "a^=b, b^=a, a^=b ;" c'est amusant de comprendre comment ça marche).

Ensuite, pour "chronométrer", il n'y a rien de complètement évident. Il faudrait une fonction qui accède au temps, non pas écoulé, mais passé par le µP dans ce thread précis. A part clock() je ne vois pas, et encore.

Et pour "visualiser" les performances en cours d'exécution, je ne vois pas ce que tu veux dire. Un bubblesort est facile à visualiser, un quicksort l'est moins. Et pour les jeux de données test, un random ne suffit pas: il faut avoir au moins un meilleur cas, un pire cas et un cas moyen (pour délimiter le domaine d'applicabilité de l'algorithme). N'oublie pas que quicksort est le plus rapide en moyenne, mais qu'il est en N² si les données sont déjà triées au départ...

-- françois

[invite7a8ce750]

Pour calculer le temps utilisateur d'une tâche, on utilise un simple

time

D'accord il faut un unix mais ça simplifie la vie ^_^

Bon sinon pour Brikkhe, c'est clair qu'il veut voir l'efficacité. Mais on peut la voir de manière statique par un calcul de complexité. Et dans le cas des tris c'est même souvent très simple (en fait c'est déjà fait). Donc parfois difficile oui fderwelt, mais dans ce cas, plutôt facile. C'est une question de cours même.

Par contre, toujours à fderwelt, je ne comprends absolument pas le rapport au sujet avec ta digression sur l'échange de deux variables.

[invite6de5f0ac]

Par contre, toujours à fderwelt, je ne comprends absolument pas le rapport au sujet avec ta digression sur l'échange de deux variables.

C'était effectivement une digression... Juste parce que l'échange de deux variables est l'opération de base du tri (avec la comparaison) et que j'aimerais bien avoir une instruction en C++ qui fasse ça directement. Mais bon, c'était juste comme ça en passant...

-- françois

[invite7a8ce750]

C'était effectivement une digression... Juste parce que l'échange de deux variables est l'opération de base du tri (avec la comparaison) et que j'aimerais bien avoir une instruction en C++ qui fasse ça directement. Mais bon, c'était juste comme ça en passant...

-- françois

Mais tu sais que si tu fais une macro swap tu auras la performance? Je ne sais pas si tu te rends compte que l'assembleur ne serait pas plus rapide.

[invite6de5f0ac]

Mais tu sais que si tu fais une macro swap tu auras la performance? Je ne sais pas si tu te rends compte que l'assembleur ne serait pas plus rapide.

Bonjour,

Oui, c'est d'ailleurs ce que je fais habituellement... Et n'importe quel bon compilo saura de toutes façons éliminer la variable intermédiaire, au besoin en passant par un registre. Mais je trouverais plus agréable, et en tout cas plus naturel, qu'une opération aussi élémentaire et courante dispose de sa propre notation (je suggérais a >< b parce que ça me paraît parlant, mais du moment que ça n'existe pas...)

-- françois

[invite7a8ce750]

Bonjour,

Oui, c'est d'ailleurs ce que je fais habituellement... Et n'importe quel bon compilo saura de toutes façons éliminer la variable intermédiaire, au besoin en passant par un registre. Mais je trouverais plus agréable, et en tout cas plus naturel, qu'une opération aussi élémentaire et courante dispose de sa propre notation (je suggérais a >< b parce que ça me paraît parlant, mais du moment que ça n'existe pas...)

-- françois

Bon perso >< me fait penser à différent et non échange. Mais bon c'est secondaire.

Maintenant je ne suis pas convaincu du bien fondé d'un tel opérateur. C'est le genre que je n'aime pas (modification de l'état des termes). Ça a tendance à être plus un danger qu'un bienfait.

Mais pourquoi pas sinon.

[abracadabra75]

Bonjour,

Et accessoirement, j'aimerais bien pouvoir écrire en C++ quelque chose comme "a >< b" pour dire "échanger a et b" sans avoir besoin d'une variable intermédiaire (au fait, pour des entiers: essaye "a^=b, b^=a, a^=b ;" c'est amusant de comprendre comment ça marche).

-- françois

Bonjour fderwelt
et tous les autres.
Tu as oublié de préciser que le signe ^ représente un 'ou exclusif'.
Tout le monde n'est pas au courant des signes logiques.

La première fois que j'ai vu cette permutation, j' ai noirci une bonne feuille de papier!
A+