Université des Sciences et Technologies de Lille
Licence Miage - Programmation 1 - TP



Algorithmes de Tris

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

5 2 8 1 3
© ¨ © ª §
 
2 5 8 1 3
¨ © © ª §
 
2 5 8 1 3
¨ © © ª §
 
2 5 1 8 3
¨ © ª © §
 
2 5 1 3 8
¨ © ª § ©
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.

5 2 4 6 1
ª ¨ § ¨ ©
2 5 4 6 1
¨ ª § ¨ ©
2 4 5 6 1
¨ § ª ¨ ©
 
2 4 5 6 1
¨ § ª ¨ ©
1 2 4 5 6
© ¨ § ª ¨

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

5 2 4 6 9 2 9 5
§ ¨ ª © ¨ § § ¨
       
5 2 4 6
§ ¨ ª ©
       
9 2 9 5
¨ § § ¨
tri¯           ¯ tri
2 4 5 6
§ ¨ ª ©
       
2 5 9 9
§ ¨ ¨ §
  fusion  
2 2 4 5 5 6 9 9
¨ § ª ª ¨ © ¨ §