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

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

Traces laissées par un Tri à Peignes sur une séquence décrcoissante {100} (worst case)

Lignes d'échanges laissées par un Tri à Peignes sur une séquence décrcoissante{100} (worst case)

Le tri à Peignes (ou tri Dobosiewicz, ou Comb sort) peut sembler similaire au tri à Bulles : il est répété à travers la séquence plusieurs fois en échangeant des pairs d'éléments. La différence est que le tri par Peignes ne sefocalise pas sur des éléments adjacents mais examine plutôt des éléments situés à une certaine distance appelée gap. Cette distance diminue progressivement au fur et à mesure que l'algorithme se poursuit.

Semblable au tri Cocktail, le tri à Peignes améliore le tri à Bulles grâce à sa capacité à traiter le «problème des tortues» (petits éléments proches de la fin de la liste ralentissant l’algorithme).
Cependant, il conserve toujours la même complexité asymptotique de calcul dans le pire des cas.

Une chose intéressante à noter cependant, ce tri est presque aussi rapide que le tri Rapide (Quick Sort) !

Le gap est d’abord égal à n, puis est réduit après chaque itération d'un facteur de rétrécissemen k jusqu'à ce qu'il atteigne la valeur 1. Par conséquent, à la fin, le tri à Peignes se comporte exactement comme le tri à Bulles.

Le facteur de rétrécissement a un effet important sur l'efficacité du tri. k = 1,3 a été suggéré comme facteur de retrait idéal par l'auteur de l'article original après des tests empiriques sur plus de 200 000 listes aléatoires. Une valeur trop petite ralentit l'algorithme en faisant inutilement de nombreuses comparaisons, tandis qu'une valeur trop grande ne permet pas de gérer efficacement les tortues car convergeant très vite à un gap de 1 (comportement du tri à Bulles).

Etapes

• 1. gap = n
• 2. Tant que chaque couple adjacent n'est pas en ordre:
• 2.a. Réduire le gap du facteur k tel que celui-ci soit toujours >= 1.
• 2.b. Comparez chaque paire d'éléments séparés par la distancec du gap et si elles sont inversées : les permuter.
• 2.c. Si le gap = 1 et aucun échange n'a été effectué : nous avons terminé.

Code

void CombSort (Iterator begin, Iterator end)
{
  auto distance = distance(begin, end);
  if (distance < 2)
    return;

  auto gap = distance;
  bool hasSwapped = true;
  while (hasSwapped)
  {
    hasSwapped = false;

    // Compute new gap
    gap /= 1.3;
    if (gap > 1)
      hasSwapped = true;
    else
      gap = 1;

    for (auto it = begin; it + gap < end; ++it)
      if (Compare(it, (it + gap)))
      {
        swap(it, (it + gap));
        hasSwapped = true;
      }
  }
}

Le tri commence la permutation avec un écart de n/1.3.
Par conséquent il échangera éventuellement n - n/1.3 éléments.

Il boucle ensuite avec un nouvel écart de n/1.3²

Quelques itérations plus tard...

À la fin, l’écart (gap) est égal à 1 (avec au moins 1 exécution) et se comporte tel un tri à bulles pour terminer le processus.

Mathématiques utiles, asymptotes du nombre harmonique généralisé H_n,r

$$H_{n,r} = \sum_{k=1}^{n} \frac{1}{k^r}$$ For $$n \approx 1$$ $$H_{n,1} \in O(log(n))$$

Temps

Meilleure

La meilleure configuration se produit lorsque tous les éléments sont déjà triés ou presque triés.
Dans ce cas, la boucle avec gap = 1 ne sera exécutée qu’une fois (comme avec les autres gaps).
Etudions les séquences pour une formulation plus pratique:

Moyenne / Pire

La moyenne et pire complexité du tri à Peignes (ou tri Dobosiewicz, ou Comb sort) est O(n²). La preuve mathématique est un peu délicate, mais a été établie en utilisant une méthode basée sur la complexité de Kolmogorov (e.g. Survey by Vitanyi, page 16).

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.