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
    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

    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
    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:
     
    Entrée : a,b,c : Entier
    Sortie : a,b,c : Entier
     
     
    Début
    si a>b alors
     
    echanger(a,b)
    finsi                  // a < b_0
     
    si b>c alors
     
    echanger(b,c)
    finsi                  // b < c && b <= b_0
     
    si a>b alors
     
    echanger(a,b)
    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 : a,b,c
    S : a,b,c trié croissant
     
    debut
    si a>b alors
      echanger(a,b) ;  // a < b_0
    fsi
    si b>c alors
      echanger(b,c) ;  // b < c && b <= b_0
      si a>b
        echanger(a,b);  // 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
    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
    je ne comprend pas l'explication, en effet pourrais-tu reprendre ton algo mais avec 3 chiffres quelconque ?

  6. #6
    Membre expérimenté
    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 
    (a) si a>b alors 
    (b)   echanger(a,b) ;  // a < b_0 
    (c) fsi 
    (d) si b>c alors 
    (e)   echanger(b,c) ;  // b < c && b <= b_0 
    (f)   si a>b 
    (g)     echanger(a,b);  // a < b < c 
    (h)   fsi 
    (i) 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
    Merci beaucoup j'ai pu enfin comprendre

  8. #8
    Nouveau membre du Club
    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
    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
    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é
    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
    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
    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é
    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(i<3){
       Si(A[i]>A[i+1]){
          B=A[i]
          A[i]=A[i+1]
          A[i+1]=B
          i=0
       }
       i=i+1
    }
    Nemerle, mathématicopilier de bars, membre du triumvirat du CSTM, 3/4 centre

  15. #15
    Nouveau Candidat au Club
    tri
    un tri qui marche bien est le tri dit 'tri par bulle'!

  16. #16
    Futur Membre du Club
    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
    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
    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
    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