ChronoMath, une chronologie des MATHÉMATIQUES
à l'usage des professeurs de mathématiques, des étudiants et des élèves des lycées & collèges

Tri élémentaire d'une suite de nombres (tri à bulles, bubble sort)       » pas de théorie, je veux utiliser le programme JavaScript | » Tri par insertion

Le langage JavaScript contient la fonction de tri L.sort() triant une liste L numérique ou non. On se propose ici de construire un algorithme de tri très simple afin de trier une liste de n nombres nombres x₁, x₂, ..., x_n à l'aide de l'ordinateur sans faire appel à la fonction intégrée au langage. Considérons 7 jetons à ranger par ordre croissant :

Passons en revue chaque élément x_i de la liste du 1er au (n-1)-ème en le comparant à tous ceux dont le rang est supérieur :

i = 1, x1 initial = 5	comparaison des rangs 1 et 2, pas d'échange :
	comparaison des rangs 1 et 3, on échange et on obtient :
	comparaison des rangs 1 et 4, on échange et on obtient le jeton n°1 à sa place, il n'y a plus d'échange :
On passe à i = 2, x2 initial = 6	comparaison des rangs 2 et 3, on échange :
	comparaison des rangs 2 et 4, on échange :
	comparaison des rangs 2 et 5, on échange et on obtient le jeton n°2 à sa place, il n'y a plus d'échange :
On passe à i = 3, x3 initial = 6	3 échanges conduisent à  :
On passe à i = 4, x4 initial = 6	2 échanges conduisent à  :
On passe à i = 5, x5 initial = 6	1 échange conduit à  :
On passe à i = 6, x6 initial = 7	1 échange conduit à la liste triée  :

L'algorithme est facile à programmer au moyen d'une simple boucle for pour i variant de 1 à n - 1, consistant à comparer les  éléments x_i, à tous les éléments x_j placés leur droite dans le ficher donné comme illustré ci-dessus. JavaScript ne connaît pas la fonction d'échange du contenu de deux variables a et b (swap sur certains langages). On la simule très simplement au moyen d'une variable auxiliaire notée ici aux :

aux = b; b = a; a =aux

 i  Le programme peut être adapté au tri d'une chaîne de caractères sans utiliser la fonction de tri intégré L.sort. Dans ce cas, l'ordre numérique usuel est remplacé par l'ordre lexicographique (celui du dictionnaire) que JavaScript connaît fort bien.

 !  
Dans ce cas les valeurs numériques perdent leur valeur arithmétique !
Par exemple 100 < 11 : ordre du dictionnaire puisque 0 < 1...
 ➔  Le programme du tri par insertion gère les deux cas

Mais pourquoi ce qualificatif de tri à bulles ?   

Dans cette méthode, le plus petit élément remonte peu à peu en première place, puis le second, etc., comme des bulles remontant à la surface d'un liquide. Seul, le plus grand élément, reste au fond...

 ➔  On peut, bien entendu trier par valeurs décroissantes, il suffit pour cela de remplacer l'instruction if (x[j] < x[i]){aux = ... par if (x[j] > x[i]){aux = ... dans la boucle d'index i du tri.

 i  En termes de complexité, le tri à bulles est un algorithme déterministe polynomial (classe P) en O(n²). C'est dire qu'il est simple mais peu efficace lorsque les données sont nombreuses. En théorie, le temps de calcul pour de grandes valeurs de n est proportionnel à n², c'est dire  que si on passe de n = 10 à n = 100 (10 fois plus de données), le temps de calcul est multiplié par 100 = 10².

En effet, dans la boucle de tri, on dénombre au maximum une dizaine d'affectations ou contrôles de variables. Attribuons un même temps de calcul δ à chacune de ces opérations élémentaires. Le nombre de comparaisons est au plus égal à :

(n - 1) + (n - 2) + ... 3 + 2 + 1 = n(n - 1)/2

Le temps de calcul global est donc de l'ordre de 5δn(n - 1), somme asymptotiquement équivalente à 5δn², proportionnel à n².