algorithme de tri
Répondre à la discussion
Affichage des résultats 1 à 11 sur 11

algorithme de tri



  1. #1
    invite8f81fa85

    algorithme de tri


    ------

    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

    -----

  2. #2
    Coincoin

    Re : algorithme de tri

    Salut,
    La moindre des choses serait de préciser le langage, non ?
    Encore une victoire de Canard !

  3. #3
    invite7a8ce750

    Re : algorithme de tri

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

  4. #4
    Brikkhe

    Re : algorithme de tri

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

  5. A voir en vidéo sur Futura
  6. #5
    invite6de5f0ac

    Re : algorithme de tri

    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

  7. #6
    invite7a8ce750

    Re : algorithme de tri

    Pour calculer le temps utilisateur d'une tâche, on utilise un simple
    Code:
    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.

  8. #7
    invite6de5f0ac

    Re : algorithme de tri

    Citation Envoyé par Gre Voir le message
    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

  9. #8
    invite7a8ce750

    Re : algorithme de tri

    Citation Envoyé par fderwelt Voir le message
    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.

  10. #9
    invite6de5f0ac

    Re : algorithme de tri

    Citation Envoyé par Gre Voir le message
    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

  11. #10
    invite7a8ce750

    Re : algorithme de tri

    Citation Envoyé par fderwelt Voir le message
    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.

  12. #11
    abracadabra75

    Re : algorithme de tri

    Citation Envoyé par fderwelt Voir le message
    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+
    Il n'y a que dans le dictionnaire où 'réussite' vient avant 'travail'.

Discussions similaires

  1. Tri selectif
    Par invite6583aa19 dans le forum Environnement, développement durable et écologie
    Réponses: 1
    Dernier message: 24/11/2007, 14h39
  2. tri
    Par invite69baa1f1 dans le forum Mathématiques du supérieur
    Réponses: 4
    Dernier message: 02/10/2007, 10h04
  3. [Biologie Moléculaire] Tri-Reagent
    Par invite4467765d dans le forum Biologie
    Réponses: 0
    Dernier message: 23/09/2007, 20h02
  4. dessein intelligent et algorithme de tri
    Par SunnySky dans le forum Science ludique : la science en s'amusant
    Réponses: 0
    Dernier message: 06/12/2006, 01h23
Dans la rubrique Tech de Futura, découvrez nos comparatifs produits sur l'informatique et les technologies : imprimantes laser couleur, casques audio, chaises gamer...