Avantages et inconvénients du tri à bulles

Les programmeurs qui passent du développement PC et Web au codage pour les appareils mobiles ou les systèmes embarqués constatent que plus de temps est consacré à la sélection et au codage de leurs propres structures de données et algorithmes. Avec moins de mémoire et un stockage de données limité, il n'y a pas de place pour des bibliothèques ou des frameworks prédéfinis. Donc, pour ceux qui ont besoin d'écrire leurs propres routines de tri, voici quelques considérations sur le choix du tri à bulles modestes.

​​Arrière-plan

Le tri à bulles est un algorithme simple qui trie une liste d'éléments en mémoire. Étant donné un tableau, le code compare à plusieurs reprises chaque paire d'éléments adjacents et les échange s'ils ne sont pas dans l'ordre. Le processus se répète jusqu'à ce qu'il n'y ait plus d'échanges. S'il était possible de visualiser le tableau pendant que le tri est en cours, les valeurs basses "gonfleraient" vers le haut tandis que les grandes valeurs descendraient vers le bas. Voici le code correspondant dans Visual Basic 2010 :

Tant que swap =True swap =False For i =0 To tbl.length - 2 If tbl(i)> tbl(i + 1) Alors tmp =tbl(i) tbl(i) =tbl(i + 1) tbl(i + 1) =tmp swap =True End If Next End While

Quand choisir le tri à bulles

Cet algorithme présente plusieurs avantages. Il est simple à écrire, facile à comprendre et ne prend que quelques lignes de code. Les données sont triées sur place, de sorte qu'il y a peu de surcharge de mémoire et, une fois triées, les données sont en mémoire, prêtes à être traitées. L'inconvénient majeur est le temps qu'il faut pour trier. Le temps moyen augmente de manière presque exponentielle à mesure que le nombre d'éléments de table augmente. Dix fois plus d'éléments prennent presque cent fois plus de temps à trier.

Autres tris de tableaux

Les algorithmes de tri varient en complexité, en vitesse et en surcharge. Le tri à bulles est le moins complexe mais aussi l'un des plus lents. D'autres tris basés sur des tableaux comme le tri par insertion et le tri par échange sont un peu plus rapides mais prennent plus de code (voir les références ci-dessous). Le principal avantage des tris basés sur des tableaux est qu'ils utilisent le moins de code et occupent le moins de mémoire de travail. Considérez ces tris pour des tableaux simples avec moins de quelques centaines d'éléments.

Algorithmes de tri complexes

Des ensembles de données plus volumineux nécessitent un code plus complexe et plus de mémoire. Le tri rapide et le tri par tas divisent et copient les ensembles de données pour optimiser le nombre de comparaisons. Le tri rapide divise continuellement la liste puis la réassemble dans un ordre trié. Le tri par tas copie les données dans une structure arborescente puis parcourt l'arbre pour recopier les données dans l'ordre. Les deux sont rapides et efficaces, mais nécessitent plus de code et beaucoup plus de stockage de travail. Choisissez ces algorithmes pour les grands ensembles de données.