Avantages et inconvénients du tri à bulles (Bubble Sort)

Les développeurs mobiles/embarqués (mémoire limitée, pas de bibliothèques) doivent parfois coder leurs propres tris. Voici les points clés sur le tri à bulles.

Principe

Algorithme simple : parcours répétitif du tableau, comparaison de chaque paire adjacente, échange si désordonné. Recommence tant qu'il y a des échanges. Les petites valeurs « remontent » (bulles), les grandes « coulent ».

Code Visual Basic 2010 :

While swap = True
    swap = False
    For i = 0 To tbl.Length - 2
        If tbl(i) > tbl(i + 1) Then
            tmp = tbl(i)
            tbl(i) = tbl(i + 1)
            tbl(i + 1) = tmp
            swap = True
        End If
    Next
End While

Quand choisir le tri à bulles

Avantages : simple à écrire, facile à comprendre, quelques lignes, tri sur place (peu de mémoire), données prêtes après tri.

Inconvénient majeur : lent. Temps moyen ~ exponentiel : 10× plus d'éléments ≈ 100× plus long.

Autres tris sur tableaux

Tri par insertion et tri par échange : un peu plus rapides, plus de code. Avantages : peu de code, peu mémoire travail. Pour tableaux simples < quelques centaines d'éléments.

Algorithmes complexes

Tri rapide (QuickSort) et Tri par tas (HeapSort) : divisent/copient pour optimiser comparaisons. QuickSort : divise récursivement puis réassemble trié. HeapSort : copie en arbre, parcours pour réordonner. Rapides et efficaces, mais plus de code et beaucoup plus de mémoire travail. Pour gros volumes de données.