Traces laissées par un Tri à Bulles sur une séquence aléatoire {50}

Lignes d'échanges laissées par un Tri à Bulles sur une séquence aléatoire {50}

Traces laissées par un Tri à Bulles sur une séquence décrcoissante {50} (pire cas)

Lignes d'échanges laissées par un Tri à Bulles sur une séquence décrcoissante {50} (pire cas)

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).

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;
  }
}

Déplacez la valeur la plus élevée à la fin en la faisant glisser successivement.

Idem avec la deuxième boucle et la deuxième valeur la plus élevée.
Comme vous pouvez le constater : une fois la boucle passée, la plage de calcul ignore le dernier élément car nous savons qu'il s'agit déjà de la valeur la plus élevée.

Quelques itérations plus tard...

L'algorithme se termine lorsque nous avons complètement itéré chaque sous-séquence : le tri est fini.

Rappel

Théorèmes mathématiques utiles:

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(n²) 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.

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.