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

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

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

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

Le tri Cocktail, tout comme le tri à Bulles, fonctionne en comparant les éléments adjacents et en les échangeant s’ils sont dans le mauvais ordre. La seule différence ici est que cela se fait dans les deux sens : sur le chemin montant nous déplaçons la plus grande valeur vers la fin du tableau puis déplaçons la plus petite valeur vers le début du tableau sur celui descendant.

De ce fait, Tri Cocktail parvient à contourner le "problème des tortues" (petits éléments proches de la fin de la liste ralentissant l'algorithme) du tri à bulles. Cependant, il conserve toujours la même complexité de calcul dans le pire cas.

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

Chaque fois que je secoue le cocktail : la valeur la plus lourde va vers le bas dans le mouvement descendant et la plus légère vers le haut dans le mouvement vers le haut.

Homonymes

• Tri à bulles bidirectionnel
• Tri Shaker
• Tri Martini
• Tri Navette

Etapes

• Tant que chaque couple adjacent n'est pas en ordre:
• 1. Comparer chaque paire d'éléments adjacents depuis le début du tableau 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).
• 1.bis. Comparer chaque paire d'éléments adjacents depuis la fin du tableau et, si elles sont inversées, les permuter.
• 2.bis. Si aucun échange n'est effectué : nous avons terminé.
• 3.bis. Supprimer le premier élément actuel des comparaisons possibles (optimization).

Code

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

  int beginIdx = 0;
  int endIdx = distance - 1;
  bool hasSwapped = true;
  while (hasSwapped && beginIdx < distance - 1)
  {
    hasSwapped = false;

    // for each element from beginning - bubble it up until the end.
    for (auto it = begin + beginIdx; it < begin + endIdx; ++it)
      if (Compare(it, it + 1))
      {
        Swap(it, it + 1);
        hasSwapped = true;
      }
    --endIdx;

    if (!hasSwapped)
      break;

    // for each element from the end- bubble it down until the beginning.
    for (auto it = begin + endIdx - 1; it >= begin + beginIdx; --it)
      if (Compare(it, it + 1))
      {
        Swap(it, it + 1);
        hasSwapped = true;
      }

    ++beginIdx;
  }
}

Déplacement de la valeur la plus élevée à la fin du tableau en l'échangeant successivement (De Gauche à Droite).

Déplacement de la valeur la moins élevée en début de tableau en l'échangeant successivement (De Droite à Gauche).
Comme nous pouvons le constater, la valeur la plus élevée et la plus basse sont maintenant exclues de la plage de traitement de l'algorithme.

Quelques itérations plus tard...

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

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

Comme pour le Tri à Bulles, le pire cas O(n²) se produit lorsque la séquence est en ordre inverse. D'abord, la valeur la plus élevée est déplacée jusqu'à la fin du tableau; puis la valeur la plus basse est glissée jusqu'au début du tableau; la boucle recommence ensuite à partir de (début + 1) jusqu'à (fin - 1) et ainsi de suite.

Mémoire

Le Tri Cocktail 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.