Lorsque les développeurs commencent à étudier les algorithmes de tri, deux noms se présentent inévitablement : Bubble Tri et Insertion Tri. Les deux sont des algorithmes élémentaires, basés sur la comparaison, qui servent de tremplin pour comprendre les techniques plus avancées. Malgré leur simplicité, ils présentent des caractéristiques de performance nettement différentes, rendant le choix entre eux dépendant du contexte. Cet article fournit une comparaison complète, analysant leurs rouages intérieurs, la complexité du temps, l'utilisation de l'espace et les applications pratiques.

Comprendre le tri de bulles en profondeur

Bubble Tri est l'un des algorithmes de tri les plus simples à conceptualiser. Il traverse à plusieurs reprises la liste, en comparant les éléments adjacents et en les échangeant s'ils sont dans le mauvais ordre. L'algorithme obtient son nom de la manière plus grands éléments -Bubble- , à la fin de la liste avec chaque passe.

Étapes algorithmiques

  1. Commencez au début du tableau.
  2. Comparez les deux premiers éléments. Si le premier est plus grand que le second, échangez-les.
  3. Déplacez-vous vers la paire suivante (positions 2 et 3) et répétez la comparaison et le swap possible.
  4. Continuez ce processus pour l'ensemble du tableau. Après un passage complet, l'élément le plus important aura été déplacé vers la dernière position.
  5. Répétez les passages, mais chaque passage ultérieur peut arrêter un élément plus tôt parce que la queue du tableau est déjà triée.
  6. Si un passage complet se produit sans échange, le tableau est trié et l'algorithme se termine tôt.

Cette optimisation de la terminaison précoce est souvent négligée dans les implémentations de base mais peut réduire le temps de la meilleure situation à O(n) lorsque l'entrée est déjà triée. Cependant, dans le pire des cas – une liste triée de manière inverse – l'algorithme fait passer une complète n], chacune exécutant jusqu'à n-1 comparaisons et échanges.

Complexité temporelle et spatiale

  • Temps le plus défavorable:[ O(n2) – se produit lorsque le tableau est en ordre inverse.
  • O(n2) – en raison des boucles imbriquées effectuant des comparaisons ~n2/2.
  • O(n) – avec l'optimisation de la terminaison anticipée et un tableau trié.
  • Complexité spatiale:[ O(1) – il trie en place en utilisant seulement une quantité constante de mémoire supplémentaire (une variable temporaire unique pour les swaps).

Bubble Tri est un algorithme stable, ce qui signifie que des éléments égaux conservent leur ordre relatif original. Cette propriété peut être importante pour certaines applications, mais la stabilité est rarement un facteur décisif en raison de son inefficacité.

Quand utiliser (théoriquement) Tri de bulles

En dehors des contextes éducatifs, Bubble Sort n'est presque jamais le meilleur choix. Ses seuls avantages sont une simplicité extrême et la capacité de détecter si l'entrée est déjà triée en un seul passage. Certains article de Wikipedia sur Bubble Sort[ note qu'il voit l'utilisation dans les graphiques informatiques pour de petites tâches où le code brivity est primordial, mais même là, Insertion Tri souvent surperforme. Pour tout ensemble de données plus grand que quelques dizaines d'éléments, la complexité O(n2) devient prohibitive.

Comprendre l'insertion tri dans la profondeur

Insertion Tri imite la façon dont les gens trient manuellement les éléments, comme organiser une main de cartes à jouer. Il construit le tableau trié final un élément à la fois en prenant à plusieurs reprises l'élément non trié suivant et en l'insérant dans sa position correcte parmi les éléments déjà triés. Cette approche réduit les comparaisons redondantes, surtout lorsque les données sont partiellement commandées.

Étapes algorithmiques

  1. Considérez le premier élément comme déjà trié (une liste d'éléments est triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée triée par triée triée triée par triée triée triée triée par triée triée triée triée par triée triée par triée par triée triée par triée par triée par triée par triée par triée par triée par triée par triée par triée par triée par triée par triée par triée
  2. Prenez l'élément suivant de la portion non triée.
  3. Comparez-le avec les éléments de la portion triée, en se déplaçant de droite à gauche.
  4. Déplacer tous les éléments triés qui sont plus grands que l'élément courant une position à droite.
  5. Insérez l'élément courant dans le point vide.
  6. Répétez les étapes 2 à 5 jusqu'à ce que le tableau entier ait été traité.

Contrairement à Bubble Tri, Insertion Tri n'effectue pas des swaps inutiles. Au lieu de cela, il déplace des éléments, qui est généralement plus efficace parce qu'il évite les frais généraux de plusieurs affectations temporaires par paire. De plus, Insertion Tri fonctionne particulièrement bien sur des données presque triées: chaque nouvel élément n'a besoin que de quelques comparaisons avant de trouver sa position correcte.

Complexité temporelle et spatiale

  • Temps le plus défavorable:[ O(n2) – lorsque le tableau est trié en ordre inverse. Chaque insertion nécessite le déplacement de tous les éléments dans la partie triée.
  • Temps moyen de la boîte : O(n2) – mais avec un facteur constant inférieur à celui de la bulle Trier en pratique.
  • Meilleure fois : O(n) – lorsque le tableau est déjà trié. Chaque nouvel élément ne compare qu'une seule fois et n'a pas besoin de changement.
  • Complexité spatiale: O(1) – en place avec une mémoire supplémentaire constante.

Insertion Tri est également stable[, en maintenant l'ordre relatif des clés égales. Sa nature adaptative – la performance s'améliore à mesure que les données deviennent plus triées – en fait un choix pratique pour les petits ensembles de données et comme une sous-routine dans des algorithmes plus sophistiqués comme Timsort.

Pertinence réelle-mondiale

Par exemple, Python , utilise Timsort, qui utilise le mode Insertion Tri pour les petits tirages. De même, Java , pour les primitifs utilise le Quicksort Dual-Pivot mais peut revenir à Insertion Tri pour les petits tirages. L'algorithme apparaît également dans les implémentations matérielles et les systèmes embarqués où la mémoire est limitée. Un aperçu détaillé peut être trouvé dans l'article Insertion Tri de Wikipedia.

Comparaison de l'efficacité entre les deux têtes

Les deux algorithmes partagent la plus grande complexité temporelle de O(n2), mais leurs performances pratiques divergent considérablement. Les principales différences résident dans le nombre de comparaisons et de mouvements, la capacité d'adaptation à l'ordre des entrées et le coût de l'échange par rapport au déplacement.

Nombre d'opérations

Bubble Tri[ effectue toujours n*[n-1-2 des comparaisons dans le pire des cas, et le même nombre d'échange (lorsqu'il est trié à l'envers). Chaque échange implique trois missions : . Cela signifie pour une liste triée à l'envers de 1000 éléments, Bubble Tri effectue ~499,500 swaps, chacun consommant trois écritures de mémoire.

Insertion Tri[ dans le pire des cas, effectue également ~n2/2 comparaisons, mais la phase =déplacement=2 est différente. Au lieu d'échanger, elle déplace les éléments en les copiant une position vers la droite. Pour une liste triée à l'envers, chaque insertion déplace une moyenne de i/2 éléments (où i est la position actuelle), ce qui entraîne environ n2/2 postes. Cependant, chaque poste est une seule affectation (surgissant l'élément suivant), et non un échange en trois étapes.

Comportement adaptatif

Insertion Tri est intrinsèquement adaptatif : si le tableau est déjà trié, il ne réalise que n-1 comparaisons et zéro décalage. Si le tableau est presque trié, il suffit d'insérer quelques éléments et ces insertions impliquent généralement des décalages courts. Bubble Tri, même avec sa terminaison précoce optimisée, effectue encore jusqu'à n passe et de nombreuses comparaisons inutiles à moins que le tableau ne soit parfaitement trié. Par exemple, considérez un tableau où seul le plus petit élément est à la fin (par exemple, . Bubble Tri va =1 sur le front sur plusieurs passages, tandis que Insertion Tri prendra simplement le 1 et l'insèrera au début d'un seul balayage.

Localité de la mémoire et cache

Les architectures modernes du CPU bénéficient d'un bon comportement cache. Insertion Tri a tendance à accéder à la mémoire séquentiellement, surtout lorsqu'il y a déplacement d'éléments contigus. Bubble Tri, cependant, échange fréquemment des éléments adjacents, qui présentent également une bonne localité, mais le nombre d'échanges provoque plus d'écritures de mémoire.

Cas d'utilisation optimale

Le choix entre ces algorithmes dépend des contraintes du problème à résoudre :

Quand le tri de bulles pourrait être acceptable

  • Démonstrations éducatives – sa simplicité aide les débutants à saisir les concepts de tri.
  • Ensembles de données extrêmement petits (=10 éléments) où les différences de performance sont négligeables.
  • Lorsque la stabilité et le tri en place sont requis, et la simplicité du code prime sur l'efficacité.
  • Exécutions de logiciels d'arrêt où l'opération d'échange peut être exécutée en parallèle (p. ex., tableaux systoliques).

Cependant, même dans ces cas, Insertion Tri est presque toujours un meilleur remplacement d'entrée avec une complexité minimale de code augmenter.

Quand l'insertion trie des brillances

  • Petits tableaux (=50 éléments) – de nombreuses bibliothèques standard passent à l'Insertion Tri pour les petites tailles en raison de ses faibles frais généraux.
  • Données triées à peu près – le tri d'insertion tourne en temps O(n) sur une entrée déjà triée ou presque triée, ce qui la rend idéale pour maintenir l'ordre après quelques mutations.
  • Tri en ligne[ – lorsque les éléments arrivent progressivement et doivent être insérés dans une liste triée, le tri d'insertion est naturel.
  • En tant que bloc de construction – dans les algorithmes hybrides comme Timsort, Insertion Tri gère les petits tirages efficacement.
  • Systèmes embarqués – où la mémoire est serrée et l'ensemble de données s'intègre dans le cache, Insertion Tri fournit de bonnes performances avec une taille de code minimale.

Pour une discussion plus détaillée des cas d'utilisation, l'article GeeksforGeeks sur Insertion Sort fournit des exemples et des variations.

Performance empirique : un simple repère

Pour établir la comparaison en nombres, envisager une expérience sur un ordinateur portable typique mettant en œuvre les deux algorithmes dans Python (bien que le comportement relatif soit maintenu dans les langues).

  • Tri bulle ~ 2,5 secondes
  • Tri d'insertion ~ 0.9 secondes

Avec 50 000 éléments, Bubble Tri devient complètement impraticable (minutes), tandis que l'insertion Tri se termine encore en quelques secondes. Sur des données presque triées (par exemple, seulement 0,1% des éléments hors de la commande), Insertion Tri peut finir en temps linéaire, tandis que Bubble Tri nécessite toujours plusieurs passages et effectue de nombreuses comparaisons redondantes.Ces résultats sont cohérents avec l'analyse de ressources comme Toptal="s Tri des animations algorithmiques, qui permettent une comparaison visuelle des comportements des algorithmes.

Analyse de complexité au-delà du grand O

Bien que la notation Big O fournisse des limites asymptotiques, elle masque des facteurs constants et des caractéristiques pratiques de performance.

Nombre de comparaisons

Dans le pire des cas, les deux algorithmes font n(n-1-2 comparaisons. Cependant, Insertion Tri effectue moins de comparaisons en moyenne parce qu'il arrête de scanner une fois qu'il trouve le point d'insertion. Bubble Tri compare toujours chaque paire adjacente dans chaque passe jusqu'à ce qu'aucun échange n'ait lieu, ce qui signifie qu'il continue souvent à faire des comparaisons même après que le tableau est trié efficacement (jusqu'à ce qu'un passage soit terminé sans échange). Insertion Tri , la logique de sortie précoce peut enregistrer près de la moitié des comparaisons dans les données aléatoires.

Nombre d'affectations

Comme mentionné, l'échange de Bubble Tris nécessite trois affectations. L'échange de Tris d'insertions nécessite une affectation par élément déplacé. De plus, l'insertion finale nécessite une affectation de plus. Pour une liste de n éléments:

  • Bubble Tri : ~ (3 * n2/2) affectations.
  • Insertion Tri: ~ (n2/2) postes + n insertions --n2/2 + n] affectations.

Ainsi Insertion Sort effectue environ un tiers de la mémoire écrit de Bubble Sort dans le pire des cas. Cela se traduit directement par une accélération du monde réel.

Impact de la distribution des données

Le tri d'insertion excelle sur les données partiellement triées car le nombre d'inversions – paires d'éléments qui sont hors de l'ordre – correspond directement à son temps de fonctionnement. Le nombre d'inversions est le nombre de déplacements. Le tri d'insertion se produira. Pour les données aléatoires, il y a environ n2/4 inversions en moyenne. Le tri d'insertion ne prend en compte que le nombre total de passages, qui est approximativement n quel que soit le nombre d'inversions (sauf si le tableau est trié).

Empreinte de mémoire et stabilité

Les deux algorithmes sont des types en place nécessitant seulement une mémoire supplémentaire O(1). Les deux sont stables, ce qui signifie que lors du tri d'une liste d'objets avec plusieurs clés, l'ordre relatif des clés égales reste inchangé. La stabilité est importante pour des applications comme le tri par plusieurs colonnes (par exemple, tri par nom de famille puis prénom). Cependant, aucun des algorithmes n'est généralement utilisé pour le tri stable à grande échelle parce que le temps O(n2) est trop lent pour les grandes n. Pour les grands ensembles de données, les types stables comme Merge Sort ou Timsort sont préférés.

Variantes et optimisations

Les deux algorithmes ont été modifiés au fil des ans :

Variantes de tri de bulles

  • Cocktail Shaker Tri – aussi connu sous le nom de Bubble Tri bidirectionnel. Il passe en haut et en bas de la liste, ce qui peut réduire légèrement le nombre de passages lorsque le plus petit élément est près de la fin.
  • Comb Tri – introduit un écart entre les éléments comparés, le transformant en une version plus simple de Shell Tri. Il améliore la performance moyenne mais reste en deçà de Insertion Tri pour les petites tailles.

Ces variantes sont rarement utilisées dans la pratique; elles restent essentiellement académiques.

Variantes de tri d'insertion

  • – utilise la recherche binaire pour trouver le point d'insertion, réduisant le nombre de comparaisons de O(n) à O(log n) par insertion. Cependant, le nombre de changements reste O(n), donc la complexité globale du temps reste O(n2).
  • Shell Tri – généralise l'insertion Tri en permettant des comparaisons d'éléments éloignés. Il a une meilleure performance asymptotique (O(n log n) dans certaines séquences de gap) et est un algorithme pratique pour les tableaux de taille moyenne.

Malgré ces variations, le tri d'insertion de base reste le point de départ pour les données petites ou presque triées.

Quand éviter les deux

Pour tout ensemble de données plus grand que quelques centaines d'éléments, ni le tri de bulles ni le tri d'insertion ne sont appropriés. A cette échelle, les algorithmes O(n log n) comme Quicksort, Fusionner Tri ou Heap Sort dominent. Même pour la taille 100, la différence entre O(n2) et O(n log n) peut être un ordre de grandeur. Par exemple, le tri de 1000 éléments avec Quicksort peut prendre 0.002 secondes, tandis que le tri d'insertion prend ~0.2 secondes et le tri de bulle ~0.6 secondes (estimations).

De plus, pour les ensembles de données extrêmement volumineux qui ne s'intègrent pas en mémoire, des algorithmes de tri externes (comme les variantes de Merge Sort) sont nécessaires. Ainsi, l'applicabilité pratique de Bubble Sort et Insertion Sort est limitée aux contextes où la taille des ensembles de données est petite ou l'entrée est presque triée.

Conclusion : Le tri d'insertion gagne presque chaque fois

Après un examen approfondi des deux algorithmes, le verdict est clair : Insertion Tri est l'algorithme plus efficace et pratique pour la grande majorité des scénarios où un simple tri O(n2) est acceptable. Bubble Tri reste un outil d'enseignement, illustrant comment des approches naïves peuvent conduire à l'inefficacité. Insertion Tri est la nature adaptative, facteur constant inférieur, et la performance supérieure sur des données presque triées en font le meilleur choix pour les petits ensembles de données, le tri en ligne, et comme sous-routine dans les algorithmes hybrides.

Les développeurs qui cherchent à implémenter un tri de zéro pour un petit problème doivent par défaut à Insertion Tri. Ceux qui ont besoin d'un tri fiable et performant pour des données arbitraires devraient compter sur des fonctions de bibliothèque comme dans JavaScript ou dans Python, qui utilisent en interne des algorithmes optimisés. Comprendre pourquoi Insertion Tri surperforms Bubble Tri équipe les programmeurs d'une compréhension plus profonde de la conception algorithmique et de l'importance des facteurs constants au-delà de Big O.

Pour plus de détails, consultez Khan Academy="S Algorithms course pour une introduction conviviale au tri de la complexité.