Le Tri à Bulles, parfois appellé tri par propagation, est un algorithme de tri simple et bien connu. Il n'est quasiment jamais utilisé en pratique mais reste cependant très utile pour faire une introduction aux algorithmes de tri.

L'algorithme compare chaque paire d'éléments adjacents, et les inverse si ils ne sont en ordre : les plus gros éléments sont "projetés" en fin de séquence.
Le passage dans la liste est répété jusqu'à ce qu'aucun échange ne soit plus nécessaire : la liste est alors triée.

Une autre façon de penser à cet algorithme de tri est la suivante:

Les valeurs les plus grandes peuvent être considérées comme plus lourdes. Elles sombrent progressivement au bas de la liste (tout comme une décantation).

Etapes

  • Tant que chaque couple adjacent n'est pas en ordre:
    • 1. Comparer chaque paire d'éléments adjacents et, si elles sont inversées, les permuter.
    • 2. Si aucun échange n'est effectué : nous avons terminé.
    • 3. Supprimer le dernier élément actuel des comparaisons possibles (optimization).

Pseudo-Code

void BubbleSort (Iterator begin, Iterator end)
{
  if (distance(begin, end) < 2)
    return;

  // Optimization: after each inner loop: the highest values already
  // is at the end of the array (reduce next loop to n-i).
  auto endIdx = -1;

  // Optimization: if no swaps needed, it indicates that
  // the list is sorted.
  bool hasSwapped;

  // For each pair of elements - bubble the greater up.
  // Then reduce the end to end - 1
  for (auto it = begin; it < end - 1; ++it, --endIdx)
  {
    hasSwapped = false;
    for (auto curIt = begin; curIt < end + endIdx; ++curIt)
      if (Compare(curIt, (curIt + 1)))
      {
        swap(curIt, (curIt + 1));
        hasSwapped = true;
      }

    // Stop if no swap needed
    if (!hasSwapped)
      break;
  }
}

Rappel

Théorèmes mathématiques utiles:

$$\sum_{i=0}^{n-1} n = n(n-1)$$ $$\sum_{i=0}^{n-1} i = \frac{n(n + 1)}{2} - n = \frac{n(n - 1)}{2}$$ $$\sum_{i=0}^{n-1} (n+i) = \sum_{i=0}^{n-1} n + \sum_{i=0}^{n-1} i$$

Temps

Meilleure

La meilleure configuration se produit lorsque tous les éléments sont déjà triés.
Par conséquent, nous ne devons parcourir la séquence qu'une seule fois : O(n).

Moyenne / Pire

Le pire cas O(n2) se produit lorsque la séquence initiale est en ordre inverse. D'abord, la valeur la plus élevée est déplacée jusqu'à la fin; puis ce sera au tour de la deuxième valeur la plus élevée et ainsi de suite.

Séquences

$$a_0 = n$$ $$a_1 = n - 1$$ $$a_2 = n - 2$$ $$...$$ $$a_i = n - i$$

Calcul

$$S(n) = \sum_{i=0}^{n-1} (n-i)$$ $$S(n) = \sum_{i=0}^{n-1} n - \sum_{i=0}^{n-1} i$$ $$S(n) = n(n - 1) - \frac{n(n - 1)}{2}$$ $$S(n) = \frac{n(n - 1)}{2}$$ $$S(n) = k(n^2 - n)$$ $$S(n) \approx O(n^2)$$

Mémoire

Le Tri à Bulles n'utilise pas de stockage ni ne fait de récursivité. Il requière donc O(1) d'utilisation mémoire dans tous les cas.