Niveau algorithmique

Arbre de décision du tri selection

Posté par
MrGrove 28-11-15 à 15:12

Bonjour tout le monde !
Je suis en 2eme année de SI et voilà la question:
Dessinez l'arbre binaire du tri par sélection.

Voilà, c'est tout. Pour ce qui est des arbres de décision des tris bulle et insertion (les seuls que j'ai trouvé sur internet) ca me parait évident, mais pour ce qui est du tri sélection je suis perdu !

Si quelqu'un peut m'éclairer je l'en remercierai ..

Posté par re : Arbre de décision du tri selection 28-11-15 à 15:22

Je viens de trouver une réponse mais j'avoue que ça ne m'aide pas à comprendre ... http://www.cs.umd.edu/~meesh/351/mount/lectures/lect16-lower-bnds-sorting.pdf

Posté par re : Arbre de décision du tri selection 28-11-15 à 19:28

On a notre liste de départ $[a_1,a_2,a_3]$
On cherche le plus petit élément de la liste.
On suppose que $a_1$ est le plus petit, puis on compare $a_1$ et $a_2$
Bonjour,

Si $a_1 \leq a_2$ alors le choix est entre $a_1$ et $a_3$ . sinon, il est entre $a_2$ et $a_3$ .
Prenons le cas où $a_1 \leq a_2$ :
Si $a_1 \leq a_3$ , alors $a_1$ est le plus petit nombre de la liste, il est donc bien placé.
Si $a_1 > a_3$ , alor s $a_3$ est le plus petit nombre de la liste. On échange donc $a_1$ et $a_3$ , et on obtient la liste $[a_3, a_2, a_1]$ . $a_3$ est bien positionné, il reste donc à étudier les deux dernières cases en comparant $a_2$ et $a_1$ .
On obtient donc bien la moitié de gauche correspondante. C'est le même principe à droite.