[Plan du site] Vous êtes ici --- > Le Site du Zéro > Les tutoriels > Non-Officiels > Programmation > Algorithmique > Le tri de Shell > Lecture du tutoriel

Le tri de Shell

Vous vous apprêtez à lire un tutoriel rédigé par un membre de ce site. Malgré tout le soin que ce membre a pu apporter au tutoriel, nous ne pouvons pas garantir que les informations contenues sur cette page sont exactes à 100%. Merci de garder cela en tête lorsque vous lirez cette page ;o)

Hello les zéros.

Apparemment si vous êtes sur ce tuto, c'est que vous avez une série d'objets à trier.
Je vous conseille, de commencer par lire le tuto de bluestorm sur le tri par insertion, dont les informations seront utiles pour ce tuto.

On peut donc commencer avec le sujet qui nous intéresse, le Tri de Shell, qui est un des meilleurs algorithmes de tri en informatique (son utilisation pour ranger un jeu de cartes est par contre un peu trop complexe

Sommaire du tutoriel :

Principe général
Exemple
Codage
Complexité
Annexes
Q.C.M.

Principe général

Le tri de Shell (Donald L. Shell) est un tri par insertion à incrémentation décroissante. o_O

Euh... ca veut dire quoi tout ça ?
Ca a l'air barbare mais c'est la description "scientifique" complète. Je vous explique ça en détails.

Shell a remarqué en 1959, que le tri par insertion classique (celui du tuto de Bluestorm) était puissant dans un cas particulier:

Lorsque la liste est presque triée

Il a aussi remarqué la chose suivante, toujours à propos du tri par insertion:

Ce tri n'est pas très rentable puisqu'il n'échange que 2 éléments par instruction

Euh? Ca veut dire quoi exactement ?

Shell a donc imaginé un tri qui garde les avantages du tri par insertion et élimine ses défauts.
Le principe est le suivant:

Les éléments qui ne sont pas à leur place, ne sont pas décalés de 1 à chaque fois, mais décalés d'un certain nombre de "cases". Le nombre de case de décalage est appelé le "pas" (gap ou step en anglais, traduction perso) Une fois qu'on a parcouru la liste, on recommence en réduisant la taille du pas jusqu'à ce qu'il vaille 1.
Quand le pas vaut 1, le tri est le même qu'un tri par insertion mais la liste est déjà presque triée grâce aux étapes précédentes.

Donc en résumé, on arrange un peu les éléments à trier avant d'appliquer le tri par insertion.

Comment on trouve le pas?

Le pas peut être choisi n'importe comment, du moment qu'il diminue à chaque étape. On pourrait très bien le faire avec un pas qui diminue de 1 à chaque fois. Mais ce n'est pas optimal, pour des raisons mathématiques compliquées, l'algorithme est le plus efficace quand le 2ème pas n'est pas un diviseur du premier et ainsi de suite.

La formule la plus utilisée pour le calcul du pas est la suivante :
Code : Autre

1	Pas_2 = (Pas_1 - 1)/3

On peut faire encore mieux avec la série suivante (trouvée empiriquement):
Code : Autre

1	701 ,301 ,132, 57, 23, 10 ,4 ,1

Attention, le pas doit toujours être un nombre entier plus grand que 0 et plus petit que le nombre d'éléments de la liste à trier

Le plus simple pour comprendre tout ça, c'est de suivre l'exemple qui suit.

Exemple

Prenons comme exemple la liste suivante et un pas de 4:
Code : Console

6 3 0 9 1 7 8 2 5 4

On compare le 1er élément avec le (1 + 4)= 5ème: 6>1 => mal placé
On inverse la position des 2 nombres:
Code : Console

1 3 0 9 6 7 8 2 5 4

On compare le 2ème élément avec le (2 + 4)= 6ème: 3<7 => bien placé
Pas d'échange et on passe au test suivant

On compare le 3ème élément avec le (3 + 4)= 7ème: 0<8 => bien placé
Pas d'échange et on passe au test suivant

On compare le 4ème élément avec le (4 + 4)= 8ème: 9>2 => mal placé
On inverse la position des 2 nombres:
Code : Console

1 3 0 2 6 7 8 9 5 4

On compare le 5ème élément avec le (5 + 4)= 9ème: 6>5 => mal placé
On inverse les 2 nombres:
Code : Console

1 3 0 2 5 7 8 9 6 4

On compare le 6ème élément avec le (6 + 4)= 10ème: 7>4 => mal placé
On inverse les 2 nombres:
Code : Console

1 3 0 2 5 4 8 9 6 7

À ce moment on arrive au bout de la liste, on doit donc calculer le nouveau pas et recommencer
On peut déjà remarquer que les petits nombres sont plutôt au début et que les grand sont vers la fin, ce qui est donc optimal pour un tri par insertion classique.

Si 2 éléments ont la même valeur, on ne les échange pas.

Calcul du nouveau pas
Le nouveau pas est donc :
Code : Autre

1	Pas_2 = (Pas_1 - 1)/3 = (4-1)/3 = 1

On se retrouve donc dans le cas d'un tri par insertion classique et je vous laisse en exercice la fin de l'algorithme :lol:

(il reste 5 échanges à faire)
Secret (cliquez pour afficher)

Les dernières étapes sont:
Code : Console

1 3 0 2 5 4 8 9 6 7 (état actuel)

0 1 3 2 5 4 8 9 6 7 

0 1 2 3 5 4 8 9 6 7

0 1 2 3 4 5 8 9 6 7

0 1 2 3 4 5 6 9 8 7

0 1 2 3 4 5 6 7 8 9

La question maintenant est: Comment coder cet algorithme ?

Codage

Langage

J'ai choisi ici de vous présenter cet algorithme en C/C++, parce que c'est sûrement le langage que vous utilisez.
Et si ce n'est pas le cas, ce ne devrait pas être trop difficile à comprendre.

Par quoi va-t on commencer ?

La première chose à faire, est de calculer le premier pas à effectuer (je préfère calculer le pas plutôt qu'utiliser la série car je peux ainsi trier un tableau de n'importe quelle taille).

On sait que:
Code : Autre

1	Pas_2 = (Pas_1-1)/3

Et que: (si n est la longueur de la liste à trier).
Code : Autre

1	... < Pas_3 < Pas_2 < Pas_1 < n

On peut donc déjà écrire une boucle pour trouver le premier pas du type:

Code : C

1
2
3

do{
    pas = (3 * pas) + 1
}while(pas<n);

Le coeur de l'algorithme

Maintenant que l'on connaît le premier pas, on peut s'occuper de l'algorithme. On va devoir exécuter l'algorithme tant que le pas est plus grand ou égal à 1, on peut donc écrire:

Code : C

while(pas >= 1){
    //algorithme à mettre
    pas = (pas - 1)/3;
}

Il ne nous reste plus qu'à coder le coeur de l'algorithme les comparaisons/échanges. On doit parcourir la liste et échanger les éléments qui sont mal placés, cela donne:

Code : C

for (i=pas;i<n;i++){
    valeur=tableau[i];
    j=i;
    while((j>(pas-1)) && (tableau[j-pas]>valeur)){
          tableau[j]=tableau[j-pas];
          j=j-pas;
          }
    tableau[j]=valeur;
}

j est une variable qui sert juste à l'échange des 2 valeurs.

Le code complet

On peut donc combiner ces trois morceaux de code, ajouter les déclarations de variables et le nom de la fonction:
Code : C

void tri_shell(int tableau[],int n)
{
        int pas(0), j, valeur;  //Création et initialisation des variables

        do{                        //Calcul du premier pas
        pas=3*pas+1;
        }while(pas<n);

        while(pas!=0)              //Tant que le pas est plus grand ou égal à 1
        {
                for (int i(pas);i<n;i++)  // On parcourt la liste
                {
                        valeur=tableau[i];
                        j=i;

                        while((j>(pas-1)) && (tableau[j-pas]>valeur)) //Et on échange les valeurs mal-placées
                        {
                                tableau[j]=tableau[j-pas];
                                j=j-pas;
                        }
                        tableau[j]=valeur;
                }
                pas=(pas-1)/3;  //On décrémente le pas
        }
}

J'ai choisi ici un tableau de taille fixe, mais on peut évidemment faire la même chose avec un vector ou une liste chainée.

Il faut utiliser une variable pour stocker la taille, sinon l'ordinateur doit la recalculer à chaque fois, ce qui implique une perte de temps (La complexité du calcul de la taille d'une liste est O(|n|), alors que celle de la lecture d'une variable est 1.

Une implémentation complète est proposée dans l'annexe 1

Complexité

Ce chapitre est assez compliqué !! Il est là à titre informatif et n'apporte rien de nouveau sur l'algorithme de tri.

Comment savoir si un algorithme est meilleur qu'un autre ?

Bonne question.

En effet, un programme dépend énormément de la machine sur lequel je le fais tourner ainsi que du langage de programmation. Il faudrait donc trouver une méthode "neutre" pour mesurer quel algorithme est le meilleur

On appelle cette mesure la complexité d'un algorithme.

C'est pour cela qu'a été créé en informatique théorique (si si ça existe je vous jure) la notation de Landau (wikipédia, assez compliqué).

Les éléments simples

On va donc apprendre à utiliser cette méthode.
On va commencer par décomposer l'algorithme en opérations simples. Ce sont les opérations basiques pour lesquels l'ordinateur n'a besoin que d'un cycle du processeur.

Exemples:

Afficher un caractère à l'écran
Changer la valeur d'une variable
Lire un caractère entré par l'utilisateur
Faire un test de condition
...

Le comptage exact du nombre d'opérations est une chose assez difficile

On sait donc décomposer un algo en une somme d'opérations simples. Et c'est là que vous me dites:
Mais ça dépend de la taille de la liste à trier !!
Effectivement, on va donc compter le nombre d'opérations et rapporter ça à la taille de la liste.

On dit que la complexité est une fonction de la taille de l'entrée

On va donc dire, par exemple, que si la taille de la liste est N, il faudra 2.5N² + 4N +3 opérations

Il reste une dernière chose à faire (et pas la plus évidente à comprendre :euh:

La notation de Landau

Si je vous dit que l'algorithme à une complexité en 3.5n + 7.22n² + 8log(n) +n³, ça peut sembler compliqué.
C'est pour ça que Landau (Edmund Landau 1877-1938) a proposé la chose suivante, on ne prend que le groupe ayant le plus haut degré car c'est le seul qui joue un rôle si n devient très grand. (On cherche le terme prépondérant quand n tend vers l'infini). On note alors:
Code : Autre

O(|n|^2)

On dit: "La complexité est en grand O de n carré"

Si je reprend l'exemple précédent : 3.5n + 7.22n² + 8log(n) +n³ donne: O(|n|³)
Quelques autres exemples:

n^2 +5n --> O(|n|²) Complexité quadratique
7.8n + 4*log(n) --> O(|n|) Complexité linéaire
log(n) + 5 --> O(log(n)) Complexité logarithmique
4.5^(n+3) --> O(|4.5ⁿ|) Complexité exponentielle
n! +34n^8 --> O(|n!|) Complexité factorielle
...

Le calcul de la notation de Landau peut devenir rapidement compliqué... comme dans notre algorithme malheureusement.

Pour ceux que ça intéresse, Si f(x) est en O(|x|²), cela veut dire que f est toujours plus petite qu'une constante C fois x². f(x) < C*x² quelque soit x.

Et notre algorithme alors ?

Il faut distinguer 2 choses pour les algorithmes de tris:
La complexité moyenne, qui est le nombre d'opérations effectuées en moyenne.
Et la complexité pire-cas, qui est le nombre d'opérations effectuées au pire. Le plus souvent le pire pour un algo de tri c'est une liste ordonnée dans l'ordre décroissant

.

Dans notre cas la complexité moyenne est:
Code : Autre

1	O(\|n\|^1.5)

En réalité, c'est pas 1.5 mais plutôt log3(2) = ln(3)/ln(2)= 1.584962501....

Et la complexité pire-cas est:
Code : Autre

O(|n|^2)

Je ne présente pas, ici, le calcul pour y parvenir, il est relativement compliqué.

L'algorithme en moyenne est donc plus rapide que le tri par insertion. Il se rapproche de l'optimum théorique qui est en:
Code : Autre

1	O(\|n*log(n)\|)

Conclusion

Si je double la taille du tableau, le temps de calcul sera multiplié par 2.828.
Si je multiplie par 10 la taille de ma liste, je devrait attendre 31.6 fois plus longtemps.

Exemple pratique

Si je possède un ordinateur doté d'un processeur 1 GHz, je peux considérer qu'une opération prendra 0.01 micro-seconde. Je peux donc faire environ 10'000'000 opérations simples par seconde.
Et donc trier un tableau de 46415 éléments. Cependant cette valeur doit être comme toujours un peu réduite, un tableau de 30000 éléments en une seconde me semble raisonnable.

Ces calculs sont à prendre à la légère. Pour atteindre un tel chiffre, il faut que le processeur soit entièrement dédié à cette tâche, il faut que la RAM puisse travailler à cette vitesse, que le BUS soit assez rapide, etc... c'est donc essentiellement théorique.

Annexes

Annexe 1

Une version complète

Cette version reprend l'exemple utilisé plus haut.

Code : C++

/* Algorithme de Tri de Shell
 * pour le site du zéro  <lien url="http://www.siteduzero.com">http://www.siteduzero.com</lien>
 * 
 * Auteur: Nanoc
 * 
 * Cette implémentation reprend l'exemple du cours.
 * Ce code n'est évidemment pas parfait, il sert juste d'exemple,
 * A vous de l'améliorer pour vos programmes
*/

#include <iostream>
using namespace std;

void tri_shell(int tableau[],int n);      //Effectue le tri
void afficheListe(int tableau[],int n);   //Affiche le tableau dans la console

const int TAILLE_LISTE = 10;

int main()
{
        int listeATrier[TAILLE_LISTE]={6,3,0,9,1,7,8,2,5,4}; //Création de la liste (identique à celle du cours)        
        
        cout <<"ETAT INITIAL:" <<endl;             //Affichage de l'etat initial
        afficheListe(listeATrier,TAILLE_LISTE);
        cout <<"***DEBUT DE L'ALGORITHME***"<<endl;  

        tri_shell(listeATrier,TAILLE_LISTE);

        cout <<"***FIN DE L'ALGORITHME***"<<endl;  

        return 0;       
}

void tri_shell(int tableau[],int n)
{
        int pas(0), j, valeur;  //Création et initialisation des variables

        do{                        //Calcul du premier pas
          pas=3*pas+1;
        }while(pas<n);

        while(pas!=0)              //Tant que le pas est plus grand ou égal à 1
        {
                for (int i(pas);i<n;i++)  // On parcourt la liste
                {
                        valeur=tableau[i];
                        j=i;

                        while((j>(pas-1)) && (tableau[j-pas]>valeur)) //Et on échange les valeurs mal-placées
                        {
                                tableau[j]=tableau[j-pas];
                                j=j-pas;
                        }
                        tableau[j]=valeur;
                        afficheListe(tableau,n); //Affichage de l'etat actuel
                }
                pas=(pas-1)/3;  //On décrémente le pas
        }
}

void afficheListe(int tableau[],int n)
{
        for(int i=0;i < n;++i){
                cout << tableau[i]<< " "<< flush;
        }
        cout << endl;
}

Une version plus souple utilisant par exemple le template <vector> sera certainement plus intéressante, néanmoins le but de ce code d'exemple est juste d'illustrer le principe de fonctionnement

Annexe 2

Une comparaison des différents algorithmes de tri:

Les tris les plus courants du plus mauvais au meilleur
Nom du tri	Complexité moyenne	Complexité pire-cas
Tri bulles	O(n²)	O(n²)
Tri par sélection	O(n²)	O(n²)
Tri par insertion	O(n²)	O(n²)
Tri de Shell	O(n^1.5)	O(n²)
Quick sort	O(n*log(n))	O(n²)
Tri fusion	O(n*log(n))	O(n*log(n))
Tri par tas	O(n*log(n))	O(n*log(n))
Optimum théorique	O(n*log(n))	O(n*log(n))

Remarque: Le tri le plus utilisé est le Quick sort (Tri rapide en français), car c'est le plus rapide en pratique pour les tableaux de taille moyenne.

Annexe 3

Liens externes sur le sujet:
Wikipédia
Un site amusant pour comparer visuellement les algorithmes de tri: lien
Et un autre dans le même genre: lien

J'espère que ce tutoriel vous sera utile pour créer vos fonctions de tris en C/C++ ou dans le langage de votre choix.

Tutoriels

Communauté

Mon compte

Recherche

Livre d'or

Publicité