Les programmeurs qui passent du développement PC et Web au codage pour appareils mobiles ou systèmes embarqués constatent qu'ils passent plus de temps à sélectionner et à coder 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 les bibliothèques ou les frameworks pré-construits. Donc, pour ceux qui ont besoin d'écrire leurs propres routines de tri, voici quelques considérations sur le choix du tri à bulles modeste.
Fond
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 en 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 faibles « bouillonneraient » vers le haut tandis que les grandes valeurs descendraient vers le bas. Voici le code correspondant dans Visual Basic 2010 :
Vidéo du jour
Tant que swap = True swap = False For i = 0 To tbl.length - 2 Si 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, il y a donc peu de surcharge 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 la table augmente. Il faut presque cent fois plus de temps pour trier dix fois plus d'articles.
Autres types de tableaux
Les algorithmes de tri varient en complexité, vitesse et surcharge. Le tri à bulles est le moins complexe mais aussi l'un des plus lents. D'autres tris basés sur des tableaux, tels que le tri par insertion et le tri par échange, sont un peu plus rapides mais nécessitent 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 prennent le moins de mémoire de travail. Considérez ces sortes pour les tableaux simples avec moins de quelques centaines d'éléments.
Algorithmes de tri complexes
Les 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 l'ordre trié. Le tri par tas copie les données dans une structure arborescente, puis parcourt l'arborescence 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.
