Exercices 6 : le tri à bulles

6.1: le tri à bulles

Rappel des notions abordées

Le tri à bulles reprend toutes les notions abordées dans les précédents exercices.

La seule nouveauté est la permutation des éléments d'un tableau et le passage d'un tableau en paramètre d'une fonction.

Lien vers les exercices

Exercice6_TriAbulle.zip

Difficulté

Un peu plus difficile, il faut bien rester concentré pour ne pas se perdre.

Enoncé de l'exercice

Le tri à bulles est une façon de trier un tableau, cette méthode n’est pas une des plus difficiles, elle n’est pas non plus une des plus rapides. Elle met en œuvre tout ce que nous avons appris.

Au départ on a un tableau non trié (5, 1, 12,-5, 16).

Tri à bulles

Au début on analyse si le premier élément est supérieur au second (5 et 1) si c’est vrai on permute les deux éléments (swap), le 1 prend la place du 5. On continue. On regarde si le deuxième élément est supérieur au troisième (ici 5 et 12). Comme 5 n’est pas supérieur à 12 on ne fait rien. On continue à regarder si on doit permuter les deux éléments contigus jusqu’à la fin du tableau.

A la fin de cette première boucle le tableau n’est pas complétement trié. Il faut recommencer à regarder si le premier élément est supérieur au deuxième puis si le deuxième est supérieur au troisième etc… A chaque fois on fait des permutations si l’élément N est supérieur à l’élément N+1. On va voir des bulles remonter d’où le nom du tri.

Quand sait-on que le tableau est trié et que l’on doit arrêter le tri?

Quand on ne fait plus aucune permutation dans le tableau (utiliser un booléen qui indique s’il y a eu des permutations).

Indications

Un des grands classiques de la programmation qu'il faut connaître, il y a plusieurs façons de trier un tableau, le tri à bulles n'est pas le plus performant mais il est assez facile à comprendre et à programmer.

C'est un des exercices les plus durs pour le BTS SIO au niveau algorithmie. Après plusieurs années il apparaît que 5% des élèves de l'option réseaux (SISR) et 50% des élèves de l'option programmation (SLAM) réussissent ce genre d'exercice.