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.

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 ?

Citation:

---

Code:

---

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:

---

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é

je ne comprend pas vraiment ton algo peux-tu l'expliquer point par point s'il te plaît

je ne comprend pas l'explication, en effet pourrais-tu reprendre ton algo mais avec 3 chiffres quelconque ?

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:

---

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

Merci beaucoup j'ai pu enfin comprendre

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 ?

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.

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

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

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

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

Trier a,b,c ?? Qu'on met dans une table A[1..3] ??

Code:

---

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 }

---

un tri qui marche bien est le tri dit 'tri par bulle'!

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

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 ! :D

--
Jedaï

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

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