Chapitre 2 : Techniques de Tris

Introduction et Objectifs

Objectif général : Bien comprendre les techniques de tris.

Objectifs spécifiques : Être capable de :

• Connaître le tri à bulle.
• Connaître le tri par sélection.
• Appliquer ces algorithmes au travers d’exercices.

I. Les tris à bulle

A) Spécification abstraite

Son principe est de parcourir une liste de valeurs en intervertissant toute paire d’éléments consécutifs non ordonnés. Ainsi après le premier parcours, l’élément maximum se retrouve en toute fin de liste.

On recommence l’opération avec la nouvelle sous-suite (en excluant le dernier élément déjà bien placé), et ainsi de suite jusqu’à épuisement de toutes les sous-suites.

Le nom de tri à bulle vient donc de ce qu’à chaque itération interne, les plus grands nombres de chaque sous-suite se déplacent vers la droite successivement, remontant à la surface comme des bulles.

B) Spécification concrète

La suite est rangée dans un tableau Tab en mémoire centrale. Le tableau va contenir une partie triée (à droite) qui va grandir, et une partie non triée (à gauche) qui va rétrécir. On effectue plusieurs fois le parcours du tableau à trier.

Le principe de base est de ré-ordonner les couples d’éléments consécutifs non classés dans la partie non triée, puis de déplacer la frontière d’une position.

Algorithme

Algorithme Tri_a_Bulles
local: i, j, n, temp Entiers naturels
Entrée : Tab Tableau d'Entiers naturels de 1 à n éléments
Sortie : Tab Tableau d'Entiers naturels de 1 à n éléments
début
  pour i de n jusqu'à 1 faire // délimite la sous-suite non triée
    pour j de 2 jusqu'à i faire // échange des couples non classés
      si Tab[j-1] > Tab[j] alors
        temp ← Tab[j-1];
        Tab[j-1] ← Tab[j];
        Tab[j] ← temp; // permutation
      Fsi
    fpour
  fpour
Fin Tri_a_Bulles

II. Tris par sélection

A) Spécification abstraite

La liste est décomposée en deux parties : une partie triée à gauche et une partie non-triée à droite.

Le principe est de parcourir la partie non-triée de la liste en cherchant l’élément minimum, puis en l’échangeant avec le premier élément de la partie non triée (l’élément frontière). Ensuite, la frontière se déplace d’une position vers la droite. C’est une récurrence sur la recherche des minima successifs.

B) Spécification concrète

On recherche l’indice de l’élément le plus petit de la partie non-triée, puis on fait un seul échange final entre l’élément à cet indice et l’élément frontière.

Algorithme

Voici la version améliorée (qui ne fait l’échange qu’à la fin de la boucle de recherche du minimum) :

Algorithme Tri_Selection

local: m, i, j, n, temp Entiers naturels
Entrée : Tab Tableau d'Entiers naturels de 1 à n éléments
Sortie : Tab Tableau d'Entiers naturels de 1 à n éléments

  pour i de 1 jusqu'à n-1 faire
    m ← i; // l'indice du minimum supposé est l'élément frontière Tab[i]
    pour j de i+1 jusqu'à n faire // on parcourt le reste
      si Tab[j] < Tab[m] alors // un nouveau minimum est trouvé
        m ← j; // on mémorise donc son indice
      Fsi
    fpour;
    temp ← Tab[m];
    Tab[m] ← Tab[i];
    Tab[i] ← temp; // on échange le minimum trouvé avec la frontière
  fpour
Fin Tri_Selection

III. Travaux dirigés

• Exercice 1 : Développer une procédure qui permet de saisir 100 réels puis qui les affiche dans l’ordre inverse de leur saisie.
• Exercice 2 : Développer une procédure qui permet de saisir 100 réels puis qui les affiche dans l’ordre croissant. (NB : Vous devez implémenter les techniques des tris à bulle et par sélection).