Aujourd'hui, vous allez faire vos gammes en algorithmique, en
programmant quatre méthodes élémentaires de tris: le tri bulle,
le tri par insertion, le tri par insertion dichotomique et le tri
fusion. Un squelette du programme est fourni. Récupérez les fichiers en tapant dans votre répertoire
cp ~touzet/ADA/Tris/*.* .
Le programme principal est tri.adb et propose un menu.
Un paquetage paq_tableau est également fourni.
Votre travail
est de compléter les quatre paquetages paq_bulle, paq_insertion, paq_insertion_dicho et paq_fusion.
Supposons que vous deviez trier un paquet de cartes.
Le tri bulle
Le tri bulle procède par parcours successifs du paquet à trier :
on étale toutes les cartes en ligne sur la table, face visible. À
chaque parcours, dès lors que deux cartes successives ne sont pas
bien ordonnées, on les échange.
Par exemple, le premier parcours est
La carte maximale, le 8 de coeur, se trouve en
fin de tableau. On réitère ce procédé sur les 4
premières cartes et ainsi de suite.
Cet algorithme ne nécessite pas de décalages, ce qui rend la
représentation contiguë par tableau particulièrement adaptée.
Le tri par insertion
L'algorithme du tri par insertion, dit-on, est le plus intuitif.
Au départ, les cartes à trier
forment un paquet sur la table. On retire une carte à la fois du paquet, pour
l'insérer à la bonne position dans la main gauche. Quand le paquet
est vide, toutes les cartes sont triées.
À chaque étape, pour savoir à quelle position insérer la
nouvelle carte, on parcourt séquentiellement les cartes de la main
gauche.
Le tri par insertion dichotomique
Le tri par insertion dichotomique est une optimisation du tri par
insertion classique : lorque l'on insère une nouvelle carte, au lieu
de parcourir séquentiellement les cartes déjà triées, on fait
une recherche dichotomique.
Le tri fusion
Le tri fusion suit la règle "diviser pour régner". On
commence par couper le paquet de cartes en deux sous-paquets.
Par un appel récursif, on trie chacun des sous-paquets.
Il ne reste plus qu'à fusionner les sous-paquets.