\begin{questions}
\item Cet algorithme ressemble à l'algorithme de tri à bulle. La différence est dans le pas de la boucle itérative (dans l'algorithme à bulle, il est égal à 1 alors qu'ici, il est variable).

L'objectif ici est de ne plus comparer uniquement les éléments adjacents d'un tableau, mais de commencer par comparer des éléments plus lointains, puis de raccourcir l'intervalle entre les éléments pour aboutir à un tri à bulle classique exécutable plus rapidement du fait que le tableau est déjà mieux trié.

Ainsi, dans le pire des cas, le coût de l'algorithme est quadratique.

\begin{Remarque}
dans le tri à bulle, les grandes valeurs en début de tableau montent rapidement vers la fin (on parle de « lièvres »), alors que les petites valeurs proches de la fin du tableau ne redescendent que très lentement vers le début (on les appelle les « tortues »).
\end{Remarque}
\enlargethispage*{5em}

\item L'instruction \texttt{gap $\leftarrow$ gap/1.3} signifie que le pas diminue de plus en plus jusqu'à valoir 1 (à l'aide de la condition \og Si gap < 1 \fg). Si on change cette valeur pour un nombre plus petit (par exemple 1.25), cela aura pour conséquence un plus grand nombre de comparaisons et donc un ralentissement de l'algorithme.

\newpage

Au contraire, si on l'augmente légèrement, par exemple en lui attribuant la valeur de 1.5, les \og tortues \fg{} ne sont pas toutes éliminées quand le pas est devenu égal à 1, et que l'on aboutit à un tri à bulle ce qui, au final, ralentit le tri.
\end{questions}

\begin{anecdote}
Ce tri est aussi appelé le \og tri de Dobosiewicz \fg, du nom de son créateur, Wodzimierz Dobosiewicz en 1980. Il a été redécouvert et popularisé par Stephen Lacey et Richard Box dans un article publié en avril 1991 dans la revue \textit{Byte Magazine}. Les auteurs de cet article ont proposé un coefficient égal à 1,3 pour une meilleure efficacité de l'algorithme.
\end{anecdote}
