Inscription / Connexion Nouveau Sujet
Niveau algorithmique
Partager :

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



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !