Le tri à peigne ou Comb Sort

Dans cet article, nous allons aborder l'algorithme du tri à peigne ou tri de Dobosiewicz (Comb Sort). Le tri à peigne a été conçu en 1980 par Wodzimierz Dobosiewicz. Il s'agit d'un algorithme de tri basé sur la comparaison qui constitue principalement une amélioration du tri à bulles. Le tri à bulles compare toutes les valeurs adjacentes, tandis que le tri à peigne élimine toutes les valeurs tortues. Les valeurs tortues sont de petites valeurs proches de la fin de la liste.

Dans le tri à bulles, il y a une comparaison entre les éléments adjacents pour trier le tableau donné. Ainsi, dans le tri à bulles, la taille de l'écart entre les éléments qui sont comparés est de 1. Le tri à peigne améliore le tri à bulles en utilisant un écart de taille supérieure à 1. L'écart dans le tri à peigne commence par la plus grande valeur et se réduit ensuite d'un facteur de 1,3. Cela signifie qu'après l'achèvement de chaque phase, l'écart est divisé par le facteur de réduction de 1,3. L'itération continue jusqu'à ce que l'écart soit de 1.

Les principales étapes pour un algorithme de tri à peigne sont les suivantes :

ÉTAPE 1 : Calculer la valeur de l'écart (gap). Si cette valeur est égale à 1 et qu'aucune autre permutation n'est possible, passer à l'ÉTAPE 4, sinon passer à l'ÉTAPE 2.

ÉTAPE 2 : Itérer sur l'ensemble des données et comparer chaque élément avec l'élément d'écart, puis passer à l'ÉTAPE 3.

ÉTAPE 3 : Permuter les éléments si nécessaire, sinon passer à l'ÉTAPE 1.

ÉTAPE 4 : Afficher le tableau trié.

Algorithme du tri à peigne

PROCEDURE tri_peigne ( TABLEAU a[1:n])
gap ← n
REPETER
    permut ← FAUX
    gap ← gap / 1.3
    SI gap < 1 ALORS gap ← 1
    POUR i VARIANT DE 1 A n AVEC UN PAS gap FAIRE
        SI a[i] > a[i+gap] ALORS
            echanger a[i] et a[i+gap]
            permut ← VRAI
        FIN SI
    FIN POUR
TANT QUE permut = VRAI OU gap > 1

Exemple de tri à peigne

Supposons que nous ayons le tableau suivant : [74, 35, 103, 57, 69, 41, 9, 17, 3]. Nous allons le trier en utilisant l’algorithme de tri en peigne.

Initialisez gap = 9

Première Itération :

permut = FAUX ; gap = 6

permut = VRAI ; gap = 6

Deuxième Itération :

permut = FAUX ; gap = 4

permut = VRAI ; gap = 4

Troisième Itération :

permut = FAUX ; gap = 3

permut = VRAI ; gap = 3

Quatrième Itération :

permut = FAUX ; gap = 2

permut = VRAI ; gap = 2

Cinquième Itération :

permut = FAUX ; gap = 1

permut = VRAI ; gap = 1

Sixième Itération :

permut = FAUX ; gap = 0 ; gap = 1

permut = FAUX ; gap = 1

L'algorithme se termine et on obtient le tableau trié suivant : [3, 9, 17, 35, 41, 57, 69, 74, 103].

Complexité de l'algorithme du tri à peigne

Complexité temporelle

• Complexité dans le meilleur des cas : Elle se produit lorsqu'aucun tri n'est nécessaire, c'est-à-dire que le tableau est déjà trié. Dans le meilleur des cas, la complexité temporelle du tri à peigne est de θ(n log n).
• Complexité moyenne : Elle se produit lorsque les éléments du tableau sont mélangés dans un ordre qui n'est ni ascendant ni descendant. La complexité en temps dans le cas moyen du tri à peigne est Ω(n2/2p), où p est un nombre d'incréments.
• Complexité dans le pire des cas : Elle se produit lorsque les éléments du tableau doivent être triés dans l'ordre inverse. Cela signifie qu'on doit trier les éléments du tableau dans l'ordre croissant, mais que ces éléments sont dans l'ordre décroissant. La complexité temporelle du tri à peigne dans le pire des cas est de O(n^2).

Complexité spatiale

La complexité en espace pour l'algorithme du tri à peigne est de O(1) car cet algorithme ne nécessite pas d’espace supplémentaire autre que des variables temporaires.

Implémentation du tri à peigne

Le code ci-dessous est une implémentation de l'algorithme du tri à peigne en langage C.

#include <stdio.h>

typedef int bool;
enum { false, true };
 
void combSort(int* tableau, int n) {
    int gap = n;
    bool permutation = true;
    int i;
   
    while (( permutation) || (gap>1)) {
        permutation = false;
        gap = gap / 1.3;
        if (gap<1) gap=1;
        for (i=0;i<n-gap;i++) {
            if (tableau[i]>tableau[i+gap]){
                permutation = true;
                // on permute les deux éléments
                int temp = tableau[i];
                tableau[i] = tableau[i+gap];
                tableau[i+gap] = temp;
            }
        }
    }
}

// fonction pour afficher les éléments du tableau
void printArr(int a[], int n) {  
    for (int i = 0; i < n; ++i)  
        printf("%d \t", a[i]);
    printf("\n");
} 

int main() {  
    int tab[] = {74, 35, 103, 57, 69, 41, 9, 17, 3};  
    int n = sizeof(tab) / sizeof(tab[0]); // n est la taille du tableau

    printf("Contenu du tableau avant le tri :\n");  
    printArr(tab, n);  
    combSort(tab, n);  
    printf("\nContenu du tableau après le tri :\n");  
    printArr(tab, n);  
}

Résultat :

L'exécution du code précédent produit le résultat ci-dessous :

Contenu du tableau avant le tri :
74     35     103     57     69     41     9     17     3     

Contenu du tableau après le tri :
3     9     17     35     41     57     69     74     103