IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Tri par ordre croissant


Sujet :

Algorithmes et structures de données

  1. #1
    Nouveau membre du Club
    Profil pro
    Inscrit en
    Décembre 2004
    Messages
    59
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2004
    Messages : 59
    Points : 25
    Points
    25
    Par défaut Tri par ordre croissant
    Bonjour voici un problème très court mais qui est un peu prise de tête:

    Ecrire un algorithme qui prend en entrée 3 entiers et qui les retourne triés par ordre croissant.

    Voici la solution que certains ont proposés mais qui me semble fausse:

    Entrée : a,b,c : Entier
    Sortie : a,b,c : Entier


    Début
    si a>b alors

    echanger(a,b)
    finsi

    si b>c alors

    echanger(b,c)
    finsi

    si a>b alors

    echanger(a,b)
    finsi

    fin


    Voici ce que j'en pense, mais à mon avis il y a trop de possibilités, c'est assez complexe à mettre en oeuvre :


    Début
    {saisie}
    Afficher ("Affichage ordonné de 3 entiers, donner le premier")
    Saisir (a)
    Afficher ("Donner le deuxième")
    Saisir (b)
    Afficher ("Donner le troisième entier")
    Saisir (c)

    Si a=b
    comparer a et c
    si a=c alors a=b=c
    si a<c alors a=b<c
    si c<a alors c<a=b

    Si a<b
    comparer a et c
    si a=c alors a=c<b
    si a<c
    comparer b et c
    si b=c alors a<b=c
    si b<c alors a<b<c
    si c<b alors a<c<b
    si c<a alors c<a<b

    Si b<a
    comparer a et c
    si a = c alors b<a = c
    si a<c alors b<a<c
    si c<a
    comparer b et c
    si b = c alors b = c < a
    si b<c alors b<c<a
    si c<b alors c<b<a

    Voilà ! ( Désolé pour la longueur ) mais le problème c'est que premièrement je trouve que ma méthode est exhaustive et deuxièmement pour mettre tout ça en algorithme ça va pas être du gâteau

    Enfin voilà ce que j'en pense,

    Merci pour votre coup de pouce, et Bravo pour le site.

  2. #2
    Rédacteur

    Avatar de khayyam90
    Homme Profil pro
    Architecte de système d’information
    Inscrit en
    Janvier 2004
    Messages
    10 369
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France, Bas Rhin (Alsace)

    Informations professionnelles :
    Activité : Architecte de système d’information

    Informations forums :
    Inscription : Janvier 2004
    Messages : 10 369
    Points : 40 164
    Points
    40 164
    Par défaut
    en quoi la solution proposée par les autres te semble-t-elle fausse ?

    à première vue elle a l'air de bien fonctionner.
    Il n'y a pas tant de cas que ça, as-tu un contre-exemple ?

  3. #3
    Membre averti

    Profil pro
    Inscrit en
    Avril 2004
    Messages
    346
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2004
    Messages : 346
    Points : 439
    Points
    439
    Par défaut
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
     
    Voici la solution que certains ont proposés mais qui me semble fausse&#58;
     
    Entrée &#58; a,b,c &#58; Entier
    Sortie &#58; a,b,c &#58; Entier
     
     
    Début
    si a>b alors
     
    echanger&#40;a,b&#41;
    finsi                  // a < b_0
     
    si b>c alors
     
    echanger&#40;b,c&#41;
    finsi                  // b < c && b <= b_0
     
    si a>b alors
     
    echanger&#40;a,b&#41;
    finsi                 // a < b < c
     
    fin
    Pourquoi serait-ce faux ? Le résultat est correct mais le dernier test peut être inutile, donc je proposerai l'algo qui fait mieux si b < c apres la permière inversion.

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
     
    E &#58; a,b,c
    S &#58; a,b,c trié croissant
     
    debut
    si a>b alors
      echanger&#40;a,b&#41; ;  // a < b_0
    fsi
    si b>c alors
      echanger&#40;b,c&#41; ;  // b < c && b <= b_0
      si a>b
        echanger&#40;a,b&#41;;  // a < b < c
      fsi
    fsi
    fin
    PS : je n'ai pas lu ton algo vu sa longueur et on obscurité

  4. #4
    Nouveau membre du Club
    Profil pro
    Inscrit en
    Décembre 2004
    Messages
    59
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2004
    Messages : 59
    Points : 25
    Points
    25
    Par défaut
    je ne comprend pas vraiment ton algo peux-tu l'expliquer point par point s'il te plaît

  5. #5
    Nouveau membre du Club
    Profil pro
    Inscrit en
    Décembre 2004
    Messages
    59
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2004
    Messages : 59
    Points : 25
    Points
    25
    Par défaut
    je ne comprend pas l'explication, en effet pourrais-tu reprendre ton algo mais avec 3 chiffres quelconque ?

  6. #6
    Membre expérimenté
    Avatar de Juju_41
    Homme Profil pro
    Développeur en systèmes embarqués
    Inscrit en
    Février 2003
    Messages
    974
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Développeur en systèmes embarqués

    Informations forums :
    Inscription : Février 2003
    Messages : 974
    Points : 1 557
    Points
    1 557
    Par défaut
    Démonstration "bourrine" de l'algo :

    Pour 3 chiffres a, b, c, sans considérer les cas d'égalités il y a 6 possibilités :
    (1) a < b < c
    (2) a < c < b
    (3) b < a < c
    (4) b < c < a
    (5) c < a < b
    (6) c < b < a

    Prenons des valeurs concrètes pour ces 6 cas :
    (1) a = 1, b = 2, c = 3
    (2) a = 1, b = 3, c = 2
    (3) a = 2, b = 1, c = 3
    (4) a = 3, b = 1, c = 2
    (5) a = 2, b = 3, c = 1
    (6) a = 3, b = 2, c = 1

    Algo proposé :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    debut 
    &#40;a&#41; si a>b alors 
    &#40;b&#41;   echanger&#40;a,b&#41; ;  // a < b_0 
    &#40;c&#41; fsi 
    &#40;d&#41; si b>c alors 
    &#40;e&#41;   echanger&#40;b,c&#41; ;  // b < c && b <= b_0 
    &#40;f&#41;   si a>b 
    &#40;g&#41;     echanger&#40;a,b&#41;;  // a < b < c 
    &#40;h&#41;   fsi 
    &#40;i&#41; fsi 
    fin
    Cas (1) : a=1,b=2,c=3
    (a) (1 > 2) faux donc on ne rentre pas dans le si
    (d) (2 > 3) faux donc idem
    Résultat a = 1, b = 2, c = 3 : le tri est correct

    Cas (2) : a=1,b=3,c=2
    (a) (1 > 3) faux
    (d) (3 > 2) vrai donc on rentre dans le si
    (e) on avait b = 3, c = 2 donc on a maintenant b = 2, c = 3
    (f) (1 > 3) faux donc on rentre pas dans le si
    Résultat : a = 1, b = 2, c = 3 : OK

    [...] Je ne vais pas tout écrire non plus [...]

    Cas (6) : a=3,b=2,c=1
    (a) (3 > 2) vrai donc on rentre dans le si
    (b) on avait a = 3, b = 2 donc on a maintenant a = 2, b = 3
    (d) (3 > 1) vrai donc on rentre dans le si
    (e) on avait b = 3, c = 1 donc on a maintenant b = 1, c = 3
    (f) (2 > 1) vrai donc on rentre dans le si
    (g) on avait a = 2, b = 1 donc on a maintenant a = 1, b = 2
    Résultat : a = 1, b = 2, c = 3 : OK

    Donc tous les cas fonctionnent ...
    Les cas d'égalité peuvent être négligés car le fait d'échanger 2 nombres égaux ne change rien au problème ... D'ailleurs le problème devrait spécifier "a <= b <= c" ou alors imposer "a <> b <> c <> a" sans quoi il serait impossible de classer a < b < c avec 2 nombres égaux ...
    Avant de poster, merci de consulter les règles du forum

  7. #7
    Nouveau membre du Club
    Profil pro
    Inscrit en
    Décembre 2004
    Messages
    59
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2004
    Messages : 59
    Points : 25
    Points
    25
    Par défaut
    Merci beaucoup j'ai pu enfin comprendre

  8. #8
    Nouveau membre du Club
    Profil pro
    Inscrit en
    Décembre 2004
    Messages
    59
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2004
    Messages : 59
    Points : 25
    Points
    25
    Par défaut
    Les seuls choses qui me sont encore obscures c'est les remarques près de l'Algo avec les symboles : //

    Là j'ai du mal à comprendre les commentaires ?

  9. #9
    Membre actif
    Profil pro
    Inscrit en
    Juillet 2004
    Messages
    849
    Détails du profil
    Informations personnelles :
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : Juillet 2004
    Messages : 849
    Points : 295
    Points
    295
    Par défaut
    L'algo de tes copains reprend le principe du triabulle.
    C'est une comparaison deux par deux qui remonte la valeur la plus haute, et aprés refait plusieurs passage.

    Imagine que tu as le même problème avec 4 variables, puis 5 etc...
    Tu verras que ta méthode risque d'être très dur a programmer.

  10. #10
    Nouveau membre du Club
    Profil pro
    Inscrit en
    Décembre 2004
    Messages
    59
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2004
    Messages : 59
    Points : 25
    Points
    25
    Par défaut
    en effet je m'en suis aperçu, d'autant qu'il y a apperement d'autres manières de tris : tri Kebbatcher je crois ......

    Mais moi dans l'algo j'aimerais bien comprendre ce que signifie les commentaires après les doubles barres : //


    Merci beaucoup

    Amicalement LaToine

  11. #11
    Membre expérimenté
    Avatar de Juju_41
    Homme Profil pro
    Développeur en systèmes embarqués
    Inscrit en
    Février 2003
    Messages
    974
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Développeur en systèmes embarqués

    Informations forums :
    Inscription : Février 2003
    Messages : 974
    Points : 1 557
    Points
    1 557
    Par défaut
    Dans les remarques de l'algo de nicolas581, il y a distinction des variables a, b, c et des valeurs initiales de ces dernières : respectivement a_0, b_0, c_0.

    Exemple concret :
    a = 1, b = 2, c = 3
    on a donc a_0 = 1, b_0 = 2, c_0 = 3
    si on échange a et b on a alors a = 2, b = 1, c = 3
    mais les constantes de valeur initiales ne changeant jamais on a toujours a_0 = 1, b_0 = 2, c_0 = 3
    Avant de poster, merci de consulter les règles du forum

  12. #12
    Nouveau membre du Club
    Profil pro
    Inscrit en
    Décembre 2004
    Messages
    59
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2004
    Messages : 59
    Points : 25
    Points
    25
    Par défaut
    Merci beaucoup j'ai compris l'ensemble,

    si quelqu'un veut correspondre avec moi sur tout ce qui est lié à l'informatique, ou quelqu'un qui est bon en Algorithmie vous pouvez me joindre au mail: bernidi31@wanadoo.fr

    Voilà @ bientôt peut-être

  13. #13
    Futur Membre du Club
    Profil pro
    Inscrit en
    Mars 2003
    Messages
    6
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2003
    Messages : 6
    Points : 7
    Points
    7
    Par défaut
    Si tu es interessée par les algos de tri, il y a pas mal de site trés bien fait sur le sujet :

    http://www.dailly.info/algorithmes-de-tri/index.php
    http://www-ipst.u-strasbg.fr/ipst/deug-ti/aide-c/tris/
    http://deptinfo.cnam.fr/Enseignement/CycleA/SD/demonstration/Tri.html

    Tizel

  14. #14
    Membre éprouvé Avatar de Nemerle
    Inscrit en
    Octobre 2003
    Messages
    1 106
    Détails du profil
    Informations personnelles :
    Âge : 53

    Informations forums :
    Inscription : Octobre 2003
    Messages : 1 106
    Points : 1 213
    Points
    1 213
    Par défaut
    Trier a,b,c ?? Qu'on met dans une table A[1..3] ??
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
     
    i=1
    Tant que&#40;i<3&#41;&#123;
       Si&#40;A&#91;i&#93;>A&#91;i+1&#93;&#41;&#123;
          B=A&#91;i&#93;
          A&#91;i&#93;=A&#91;i+1&#93;
          A&#91;i+1&#93;=B
          i=0
       &#125;
       i=i+1
    &#125;
    Nemerle, mathématicopilier de bars, membre du triumvirat du CSTM, 3/4 centre

  15. #15
    Nouveau Candidat au Club
    Profil pro
    Inscrit en
    Décembre 2004
    Messages
    1
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2004
    Messages : 1
    Points : 1
    Points
    1
    Par défaut tri
    un tri qui marche bien est le tri dit 'tri par bulle'!

  16. #16
    Futur Membre du Club
    Profil pro
    Inscrit en
    Mars 2003
    Messages
    6
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2003
    Messages : 6
    Points : 7
    Points
    7
    Par défaut Re: tri
    Citation Envoyé par le_castor
    un tri qui marche bien est le tri dit 'tri par bulle'!
    Pour 3 valeurs, tous les tris ce valent, mais pour trier une grande liste, le mieux est sans nul doute le tri rapide (quick short) et pour trier des listes d'entiers, le tri par casier est ce qui est le plus rapide.

    Tizel

  17. #17
    Expert éminent
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2003
    Messages : 6 245
    Points : 8 586
    Points
    8 586
    Par défaut
    Pas tout à fait d'accord, le tri fusion est meilleur que le quicksort, puisqu'il est toujours de complexité en O(n*log n), contrairement au quicksort qui dégénère (relativement) facilement jusqu'en O(n^2)... Après tout dépend de la structure de donnée que tu as à manipuler, le tri fusion n'étant pas génial avec les tableaux.
    Par contre évidemment je suis d'accord pour le tri casier, c'est de loin le meilleur quand il est applicable !

    --
    Jedaï

  18. #18
    Futur Membre du Club
    Profil pro
    Inscrit en
    Mars 2003
    Messages
    6
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2003
    Messages : 6
    Points : 7
    Points
    7
    Par défaut
    Citation Envoyé par Jedai
    Pas tout à fait d'accord, le tri fusion est meilleur que le quicksort, puisqu'il est toujours de complexité en O(n*log n), contrairement au quicksort qui dégénère (relativement) facilement jusqu'en O(n^2)
    Le tri fusion est de complexité n*lg(n) dans tous les cas. Dans le meilleur, comme dans le pire.
    Le tri rapide, est de complexité n*lg(n) en moyenne. Dans le meilleur des cas, il est de complexité n, dans le pire, de complexité n^2.

    Par contre, si tu considére l'espace mémoire et sa gestion, le tri fusion est généralement beaucoup plus gourmand.

    Il faut faire un choix entre ces deux tri en fonction du type de machine sur lequel l'application tourne (PC avec beaucou de mémoire ou embarqué avec peu de mémoire) et des performances que l'on souhaite (le n*ln(n) en moyenne suffit il, ou veux ton l'avoir de façon certaine ?).

    Tizel

  19. #19
    Futur Membre du Club
    Profil pro
    Inscrit en
    Décembre 2008
    Messages
    8
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2008
    Messages : 8
    Points : 5
    Points
    5
    Par défaut
    Bonjour

    Je me permet de reprendre ce vieux post pour le meme theme " trier 3 nombres"

    Ma question est : Peux ton utiliser l'operation ET dans le Si

    Je n'ai vu ca nullepart donc je me doute que j'ai faux; voila ce que j'ai fait :

    Je me suis dit : a, b, c trois nombres

    probabilité : on a ces classements
    a>b>c
    a>c>b
    b>a>c
    b>c>a
    c>a>b
    c>b>c

    A savoir qu'on veut finalement classer les trois nombres croissant
    c<b<a

    Mon algo serait donc :

    Début

    Afficher ("Saisir trois entiers différents")
    Saisir (a,b,c)
    Si
    a>b et b>c
    Alors
    a <- c
    b <- b
    c <- a
    Finsi
    Si
    a>b et a>c et c>b
    Alors
    a <- a
    c <- b
    b <- c
    Finsi
    Si
    b>a et a>c
    Alors
    b <- c
    a <- b
    c <- a
    Finsi
    Si
    b>a et b>c et c>b
    Alors
    b <- c
    a <- a
    c <- b
    Finsi

    //etc .....

    Afficher ( "Le classement croissant est :", c, b, a)
    Fin

Discussions similaires

  1. codage d'un tri par ordre croissant
    Par babou466 dans le forum Macros et VBA Excel
    Réponses: 7
    Dernier message: 05/03/2009, 11h48
  2. Tri par ordre croissant
    Par identifiant_bidon dans le forum Général JavaScript
    Réponses: 5
    Dernier message: 27/02/2008, 14h11
  3. Analyse croisée : empêcher le tri par ordre croissant
    Par mouaa dans le forum Requêtes et SQL.
    Réponses: 0
    Dernier message: 19/02/2008, 15h08
  4. Tri par ordre croissant
    Par controle55 dans le forum x86 16-bits
    Réponses: 4
    Dernier message: 12/01/2008, 22h16

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo