Attention ! cette page va être migrée vers https://lwh-21.github.io/Algos/
Le tri à peigne est un algorithme de tri par comparaison qui améliore de façon notable les performances du tri à bulle. Cet algorithme fut conçu en 1980 par Włodzimierz Dobosiewicz. Quelques années plus tard, en 1991, Stephen Lacey et Richard Box ont montré dans un article dans Byte Magazine que l'idée de Donald Shell pouvait s'appliquer également, et avec autant de bénéfices, au tri bulle.
Le principe est de ne plus comparer uniquement des éléments adjacents, mais de commencer par comparer des éléments plus lointains, puis de raccourcir progressivement l'intervalle entre les éléments pour aboutir finalement à un tri à bulle classique.
L'animation ci-après détaille le fonctionnement de ce tri :
Le choix du facteur de réduction est primordial pour l'efficacité de cet algorithme. En général, on prend un facteur de réduction compris entre 1.25 et 1.33. L'animation ci-dessus utilise 1.3 comme facteur de réduction.
Cet algorithme n'est pas stable, comme vous pouvez le vérifier ici.
Si on applique cet algorithme au petit jeu de la page précédente, on obtient :
Comme pour le tri de Shell la complexité du tri à peigne est très difficile à calculer. On considère généralement que, dans le meilleur des cas, elle est linéaire (en O(n)), et que, dans le pire des cas elle est en Θ(n2). En moyenne elle serait en en O(n log n).
L'application Javascript ci-dessous permet d'évaluer le nombre d'échanges et de comparaisons nécessaires à l'algorithme pour trier une liste. Choisissez le mode de génération de la série à trier, le facteur de réduction, la couleur de la courbe et cliquez sur "calculer". Jusqu'à cinq courbes peuvent être affichées sur le même graphique.Dans le cas de données générées aléatoirement, l'application effectuera jusqu'à dix passes, pour calculer la moyenne des comparaisons et des déplacements.
Taille données | Gaps | Passe | Nombre comparaisons | Nombre échanges | Total |
---|---|---|---|---|---|
0 | 0 | 0 |
Taille données | Gaps | Passe | Nombre comparaisons | Nombre échanges | Total |
---|---|---|---|---|---|
0 | 0 | 0 |
Taille données | Gaps | Passe | Nombre comparaisons | Nombre échanges | Total |
---|---|---|---|---|---|
0 | 0 | 0 |
Taille données | Gaps | Passe | Nombre comparaisons | Nombre échanges | Total |
---|---|---|---|---|---|
0 | 0 | 0 |
Taille données | Gaps | Passe | Nombre comparaisons | Nombre échanges | Total |
---|---|---|---|---|---|
0 | 0 | 0 |