TP-Cours ITC 05

Tri à bulles ou «sinking Sort»

I. Généralités, premiers pas vers un algorithme

Trier des données consiste à les ranger suivant un ordre (total) défini au préalable. Cela peu être le tri des mot d’un dictionnaire suivant l’ordre alphabétique ou le tri d’un tableau d’entier selon l’ordre croissant usuel. Cet ordre total utilisé pour trier des éléments d’une structure de données sera appelé clé du tri.

On s’intéressera ici au tri par ordre croissant usuel d’une liste/d’un tableau d’entiers, c’est-à-dire que la liste $L$ de longueur $n \in N^{*}$ sera considérée comme triée si pour tout $(i, j) \in [[0; n - 1]]^{2}$ , $i ⩽ j ⟹ L [i] ⩽ L [j]$
Cette propriété revient également à dire que pour tout $i \in [[0; n - 2]], L [i] ⩽ L [i + 1]$ .

Mais alors, le tri à bulles ou "sinking Sort", c'est quoi au juste ?

Une première réponse dans cette "danse hongroise"

Le sinking Sort/tri à bulles doit son nom au fait qu’il déplace le plus grand élément d’un tableau (le plus lourd, le premier à couler) « au fond » de ce tableau, puis le second plus grand élément en avant-dernière position, etc … On peut également voir ces déplacements d’éléments comme le mouvement de bulles d’air qui remonteraient (d’abord la plus grosse bulle, puis la seconde plus grosse, etc …) à la surface d’un liquide.

Le tri à bulles consiste à parcourir plusieurs fois le tableau $L$ (on parle de passes successives), par exemple de gauche à droite, en comparant les éléments côte à côte (i.e. consécutifs) et en les permutant s’ils ne sont pas dans le bon ordre. Ainsi, après la première passe, le plus grand élément du tableau se retrouve en dernière position.

Voici l’algorithme correspondant au premier parcours du tableau :

Pour aller plus loin et comprendre ce qui se passe lors du second parcours du tableau, du troisième parcours, etc … suivez attentivement la vidéo ci-dessous, cela ne durera pas plus de 2 minutes !

Après le premier parcours de la liste $L$ , l’algorithme du tri à bulles a déplacé le plus grand élément de la liste en dernière position. Après le deuxième parcours, le plus second plus grand et le plus grand élément de la liste sont placés dans cet ordre en avant dernière et dernière position.

Notons $n \in N^{*}$ le nombre d’éléments de $L$ . Si $k \in [[1; n - 1]]$ , alors après $k$ parcours de la liste, les $k$ plus grands éléments de $L$ sont rangés par ordre croissant en fin de liste. Cela signifie qu’au $k$ -ième parcours, on ne s’occupera pas des $k - 1$ derniers éléments de $L$ puisque ceux-ci sont déjà bien positionnés.

Exemple : $L = [22, 34, 29, 15, 6]$

Dans cet exemple, on a appliqué un tri à bulles pour ranger par ordre croissant les éléments de la liste $L = [22, 34, 29, 15, 6]$ . Ce tri a été effectué en quatre parcours de $L$ puisque cette liste contient 5 éléments entiers. À chaque étape de l’algorithme, on a représenté en rose les éléments que l’on compare pour les échanger s’ils ne sont pas rangés selon l’ordre usuel. À la fin de chaque parcours, un élément du tableau prend sa place définitive dans le tableau trié et sera représenté en vert lors des parcours suivants.

Ainsi, vous l’avez compris, les parcours successifs de $L$ sont de plus en plus courts car on n’examine plus les éléments déjà « bien placés » qui ont été déplacés, lors des parcours précédents, en fin de liste. On effectue une comparaison d’éléments en moins à chaque parcours : sur notre exemple, il y a 4 comparaisons lors du premier parcours, 3 lors du deuxième, 2 lors du troisième parcours et 1 pour le dernier.

Ce nombre de comparaisons sera appelé complexité de l’algorithme et nous permettra de déterminer un « temps de calcul » de notre algorithme sur un tableau/une liste de longueur $n \in N^{*}$ . Cette complexité pourra être comparée à la complexité d’autres algorithmes de tris que nous étudierons cette année.

II. Fonction Python, complexité de l'algorithme

L’algorithme de tri à bulles comporte une structure de 2 «boucles imbriquées». La première boucle (

for

for) porte sur le numéro de parcours $k$ de la liste.

Question 1

Si on note $n \in N^{*}$ le nombre d’éléments de la liste $L$ , le numéro de parcours $k$ de la liste dans l’algorithme décrit précédemment varie entre $a$ et $b$ que vous devez déterminer. Ainsi, l’entête de la première boucle sera

for k in range(...,...):

for k in range(...,...):

Compléter le code précédent en remplaçant les … par les expressions imposées par les valeurs de $a$ et $b$ .

Nous avons vu que lors du premier parcours, on est amené à comparer $L [i]$ et $L [i + 1]$ pour tout $i$ variant de 0 à $n - 2$ .

Question 2

Lors du parcours n° $k \in [[1; n - 1]]$ , on compare $L [i]$ et $L [i + 1]$ pour tout $i$ variant de 0 à … . Compléter la phrase précédente en remplaçant … par une expression fonction de $k$ et de $n$ .

À l’aide des deux questions précédentes et de l’algorithme donné dans la partie I, écrire la fonction Python

triABulles(L:list)⟶None

triABulles(L:list)⟶Nonequi modifie la liste d’entiers

L

pour qu’elle soit ordonnée à l’aide de l’algorithme du tri à bulles et ne renvoie aucune valeur (

return None

return None).

Vous pourrez tester votre fonction sur la liste $L = [22, 34, 29, 15, 6]$ puis lancer une batterie de tests sur votre fonction afin de valider son utilisation sur divers exemples.

On souhaite à présent compter le nombre de comparaisons effectuées sur des éléments de $L$ de longueur $n \in N^{*}$ lors de l’appel

triABulles(L)

triABulles(L). Une comparaison entre deux éléments de

L

a lieu chaque fois que le test

if L[i]>L[i+1]

if L[i]>L[i+1] est effectué.

Ainsi, il y a autant de comparaisons entre éléments de $L$ que de couples $(i, j)$ dans la structure de boucles imbriquées, c’est-à-dire : $\sum_{k = 1}^{n - 1} \sum_{i = 0}^{n - 1 - k} 1 = \sum_{k = 1}^{n - 1} (n - k) = 1 + 2 + 3 + \dots + n - 1 = \frac{n (n - 1)}{2} \underset{n \to + \infty}{\sim} \frac{n^{2}}{2}$

On dit que la complexité de cet algorithme est de l’ordre de $n^{2}$ ou en $O (n^{2})$ et on parlera de complexité quadratique.