Tri à bulles et tri par insertion

Le tri à bulles et le tri par insertion sont en O(n²) dans le pire cas, ce qui les rend peu adaptés aux entrées volumineuses. Pourtant, tout entretien sérieux sur les algorithmes attend de vous que vous sachiez les implémenter et les analyser. Ils enseignent des concepts fondamentaux — comparaison, échange, tri stable et comportement dans le meilleur cas — qui s’appliquent à des algorithmes plus avancés. Les examinateurs les utilisent pour vérifier que vous savez raisonner sur les invariants de boucle et la notation asymptotique à partir des principes fondamentaux.

Le tri à bulles parcourt plusieurs fois le tableau et échange les éléments adjacents qui ne sont pas dans le bon ordre. Après chaque passage complet, le plus grand élément non trié « remonte » jusqu’à sa position finale à la fin du tableau. Après n-1 passages, le tableau entier est trié. Son nom vient de la façon dont les éléments les plus grands remontent comme des bulles. C’est l’algorithme de tri le plus simple à décrire, mais il est rarement utilisé en pratique.

Une version optimisée du tri à bulles utilise un indicateur swapped : si un passage interne complet n’effectue aucun échange, le tableau est déjà trié et l’exécution s’arrête immédiatement. Cela donne un meilleur cas en O(n) pour une entrée déjà triée — le seul véritable avantage du tri à bulles. Sans cet indicateur, l’algorithme effectue toujours O(n²) comparaisons. L’optimisation par arrêt anticipé est ce que les examinateurs vérifient lorsqu’ils demandent comment améliorer le tri à bulles.

La boucle externe du tri à bulles s’exécute n-1 fois. La boucle interne s’exécute n-1-i fois à chaque passage : (n-1) + (n-2) + ... + 1 = n(n-1)/2 ≈ n²/2 comparaisons. Cela donne une complexité de O(n²) en moyenne et dans le pire cas. Avec l’indicateur d’arrêt anticipé, le meilleur cas passe à O(n) pour une entrée triée. La complexité en espace est O(1) — seul l’échange nécessite une variable temporaire. Le tri à bulles est stable : les éléments égaux conservent leur ordre relatif, car seuls les éléments strictement supérieurs sont échangés.

Le tri par insertion imite le tri d’une main de cartes : prenez la carte suivante (l’élément) et insérez-la à la bonne position parmi les cartes déjà triées à gauche. L’invariant est que arr[0:i] est toujours trié. Pour chaque nouvel élément, décalez les éléments plus grands vers la droite afin de lui faire une place. Cet algorithme en place et stable a une complexité de O(n²) dans le pire cas, mais de O(n) dans le meilleur cas pour des données presque triées.

Suivez le tri par insertion sur [3, 1, 4, 2] : i=1, clé=1, décalez 3 vers la droite → [1, 3, 4, 2]. i=2, clé=4, aucun décalage → tableau inchangé. i=3, clé=2, décalez 4 puis 3 vers la droite → [1, 2, 3, 4]. Chaque élément est comparé à ceux qui se trouvent à sa gauche jusqu’à trouver sa position correcte. La boucle interne while effectue les décalages à l’aide d’affectations, qui sont plus rapides que les échanges puisqu’un décalage nécessite une affectation, contre trois pour un échange.

L’atout majeur du tri par insertion est sa complexité de O(n + inversions). Une inversion est une paire (i,j) telle que i < j mais arr[i] > arr[j]. Pour les tableaux presque triés qui ne contiennent que quelques inversions, le tri par insertion est extrêmement rapide — parfois plus rapide en pratique que le tri fusion grâce à sa simplicité et à son accès au cache favorable. Le Timsort de Python utilise le tri par insertion sur les petits sous-tableaux, précisément pour cette raison.

Un algorithme de tri est stable si les éléments égaux conservent leur ordre relatif initial après le tri. Le tri à bulles et le tri par insertion sont tous deux stables : ils n’échangent jamais les éléments égaux. La stabilité est importante lorsque vous triez successivement selon plusieurs clés : triez d’abord selon la clé secondaire, de manière stable, puis selon la clé primaire, également de manière stable, afin de conserver l’ordre lié à la clé secondaire entre les éléments ex æquo. Le tri fusion est lui aussi stable ; le tri par tas et le tri rapide ne le sont généralement pas.

La boucle interne du tri par insertion trouve à la fois la position correcte et décale les éléments. Vous pouvez utiliser une recherche binaire pour trouver la position en O(log i) comparaisons, mais les décalages prennent toujours O(i) : la complexité globale reste donc O(n²). Cette optimisation réduit le nombre de comparaisons, ce qui est utile lorsque les fonctions de comparaison sont coûteuses, mais elle ne réduit pas le nombre total d’opérations. Ce « tri par insertion binaire » apparaît dans Timsort pour les petites tailles de blocs.

Lors des entretiens, énoncez cette comparaison avec assurance : le tri par insertion est strictement meilleur que le tri à bulles — les deux sont en O(n²) dans le pire cas et utilisent O(1) d’espace, mais le tri par insertion effectue moins d’écritures (O(n+k) pour k inversions contre O(n²) pour le tri à bulles), est plus adapté au cache et constitue le choix pratique pour les petites valeurs de n (Timsort l’utilise). Le seul véritable avantage du tri à bulles est sa simplicité pédagogique. En production, utilisez toujours le tri intégré au langage.

Le nombre d’inversions dans un tableau est égal au nombre de paires (i,j) telles que i < j mais arr[i] > arr[j]. Le tri par insertion effectue exactement autant de décalages qu’il y a d’inversions — une observation utile. Compter efficacement les inversions, en O(n log n), nécessite un tri fusion modifié. Les examinateurs demandent parfois, pour approfondir une discussion sur le tri : « Dans quelle mesure votre algorithme tient-il compte des inversions ? »

Vérifiez votre compréhension des concepts de Structures de données & algorithmes — préparation aux entretiens de programmation présentés dans cette leçon.

Dans cette leçon, vous avez appris que : le tri à bulles effectue n-1 passages, chacun faisant remonter le maximum actuel jusqu’à sa position finale, avec une complexité de O(n²) dans le pire cas mais de O(n) dans le meilleur cas grâce à l’indicateur d’arrêt anticipé ; le tri par insertion décale les éléments vers la droite pour insérer la clé actuelle à la bonne position dans la partie triée, en O(n + inversions), ce qui le rend optimal pour les données presque triées ; et les deux algorithmes sont stables, utilisent O(1) d’espace et ont une complexité de O(n²) dans le pire cas — mais le tri par insertion est strictement préférable au tri à bulles dans toutes les situations pratiques. Nous allons maintenant implémenter le tri fusion à partir de zéro.