Introduction

Cette leçon aborde les algorithmes de tri. Nous utiliserons un jeu de carte, pour certains exemples. Si vous en avez un sous la main, ça pourra vous aider à mieux comprendre les différents alogorithmes analysés.

Le tri est un domaine d'étude très important en informatique. Comme nous l'avons vu dans la leçcon précédente sur les techniques de recherche, il est bien plus rapide de faire une recherche dans une liste quand elle est ordonnée. Le Tri est le processus qui va permmetre de mettre des objects dans l'ordre.

Un des algorithmes le plus simple est le tri par bulle. Voici une vidéo qui montre le tri de 13 cartes à jouer avec cette technique. En regardant la vidéo, essayez de découvrir et comprendre l'algorithme.

Le tri à bulle est un exemple de tri par comparaison. La méthode consiste à répéter la comparaison de deux cartes, à mettre la plus petite sur la pile de gauche et conserver la plus grande. A la fin de la pile, la dernière (donc la plus grande)est posée sur la pile triée. Puis on recommence avec la pile de gauche. Comme vous pouvez le voir, le tri par bulle nécessite de faire plusieurs passes sur la liste de cartes.

Le tri par bulle tire son nom de l'analogie avec les bulles d'air qui montent dans l'eau. C'est d'abord la plus grosse qui fait surface, puis celles de taille décroissante avec le temps ou les passes. Dans l'exemple, montré ci-dessus dans la vidéo, à la première passe, c'est l'As qui est placé dans la pile triée à droite. A la seconde passe, c'est la Reine qui rejoint la pile de droite, et ainsi de suite.
L'illustration ci-contre issu de Wikipedia , donne un autre exemple avec le tri de batons de tailles différentes.

Pseudocode du tri à bulles

Voici une description du pseudo code correspondant au tri par bulle illustré par la vidéo :

Pour faire le tri par bulle d'u jeu de N cartes :
Placez le jeu de cartes, faces vers la table, dans une pile de droite.
Répétez N fois
    Prenez la carte du dessus dans la main gauche.
    Répétez jusqu'à ce qu'il n'y ait plus de cartes dans la pile de droite.
        Si la carte de la main gauche est plus grande que la prochaine carte de la pile de droite
            Placez cette dernière dans la pile de gauche.
        Sinon
            Placez la carte en main gauche sur la pile de gauche, et gardez l'autre.
    Quand la passe (pile), mettez la carte qui vous reste sur la pile des cartes triées.
    Déplacez la pile de gauche sur la droite.

Activité

Si vous avez un jeu de cartes, essayez l'algorithme du tri à bulles pour trier quelques cartes (six ou sept).

Tri par Fusion

Le Tri Fusion est un autre algorithme de tri par comparaison. Il tire son nom qu fait que l'on porécède par fusion de piles de cartes. Essayez de voir si vous pouvez suivre l'algorithme.

Comme vous le voyez, le tri par fusion commence avec des piles de 1 carte. Puis, à chque passe, on fusionne par piles de 2 cartes, puis 4 cartes, puis 8 et ainside suite, jusq'à la fusion des cartess en un seul paquet qui est trié. Vous aurez probablement remarqué que ça va bien plus vite que le tri à bulles.
L'illustration ci-contre issue de Wikipedia , donne un autre exemple avec le tri de batons de tailles différentes.

Pseudocode du tri fusion

Voici une description du pseudo code correspondant au tri par fusion illustré par la vidéo :

Pour faire un Tri par Fusion d'un jeu de N cartes:
Séparez les cartes en N piles de une carte chaque.
Répéter jusqu' à ce qu'il y ait 1 seule pile de N cartes :
    Fusionner les piles adjacentes (avec un tri par comparaison) en piles de fois plus grosses.

Comme vous le voyez, le Tri Fusion, comme la recherche dichotomique (cf. leçon précédente), est un exemple de résolution de problème avec une approche de type diviser pour régner, qui tires son nom du fait que l'on décompose un gros problème en problèmes plus petits que l'on résoud ensuite. Dans ce cas, le jeu de cartes est divisé en piles de 1 carte avant de commencer la fusion.

Activité

Si vous avez un jeude cartes, essayez le tri fusion. Vous pouvez tester l'algorithme avec 16 cartes, pour avoir toujours le même nombre de cartes dans les piles.

Le tri par paquets : Un Non "Comparif"

Les algorithmes de tri ne font pas toujours des comparaisons. Un exemple de tri Non-comparatif, est le tri par paquets, qui utilise des caractéristiques des valeurs à trier pour les placer dans des paquets distincts. Les paquets sont ensuite rassemblés.

Dans cette vidéo, les paquets correspondent à la valeur des cartess -- i.e., 2, 3, Valet, As, etc.

Comme vous le voyez, le rangement par paquet ne compare pas les cartes entre elles. L'algorithme utilise plutôt la valeur des cartes pour les ranger dans le paquet approprié. Une fois que toutes les cartes sont dans leur paquet, on eassemble ce spaquets dans l'ordre. Ce type de tri est le plus rapide des trois exemples que nous avons décrits.

Pseudocode du tri par paquets

Pour que le tri par paquets fonctionne, il faut être en mesure de faire le calcul qui identifie le paquet dans lequel ranger chacun des items à trier, à partir des caractéristiques de cet item. Par exemple, nous pouvons associer à chaque carte le numéro suivant en fonction de sa valeur :

Carte	2	3	4	5	6	7	8	9	10	Valet	Dame	Roi	As
Bucket	2	3	4	5	6	7	8	9	10	11	12	13	14

Nous avons simplement donné une valeur numérique (ou un rang ou rank en anglais) àa chaque valeur de carte. Maintenant, si nous avons 13 paquets, numérotés de 2 à 14, nous pouvons utiliser l'algorithme suivannt pour faire le tri :

Pour faire le tri par paquets d'un jeu de N cartes:
1. Ranger chaque carte dans le paquet correspondant à son rang.
2. Rassembler les cartes dans l'ordre du rang des paquets encommençant par le paquet de rang inférieur.

Activité

C'est tout! Assez simple, non ? Si vous avez un ju de cartes, essayez avec le jeu complet de 52. Après la première étape, le paquet numéro 2 devrait contenir tous les 2. Le paquet numéro 14 tous les As. Si vous rassemblez les cartes en commençant par le paquet 2, puis 3, puis 4, etc. le jeu de cartes sera tré à la fin.

Tri par base

Le tri par paquet est un exemple de méthode plus générale de tri non-comparatif appelé Tri par base (ou radix). L'idée sous-jacente est de trier les nombres en fonction de leurs digits.

Par exemple, supposons que nous voulions trier la liste de nombres suivants à 2-digit numbers (0 à 99). Pour faciliter la lecture nous avons rajout le 0 des dizaines pour les nombres de 1 à 9:

25 26 01 31 24 22 17 16 07 09

On commence par les mettre dans des paquets en fonction de leur digit le moins significatif (celui des unités).

Paquets	0s	1s	2s	3s	4s	5s	6s	7s	8s	9s
Valeurs		01	22		24	25	26	17		09
		31					16	07

Maintenant si nous reprenons les paquets de nombres, de gauche à droite left et du dessus au dessous dans chque paquet nous récupérons la list e des ombres dans l'ordre suivant :

01 31 22 24 25 26 16 17 07 09

Maintenant recomençons mais en utilisant comme le digit de gauche celui des dizaines)pour choisir le paquet:

Paquets	0s	1s	2s	3s	4s	5s	6s	7s	8s	9s
Values	01	16	22	31
	07	17	24
	09		25
			26

Si nous reprenons les paquets de nombres, de gauche à droite left et du dessus au dessous dans chaque paquet nous récupérons la liste des nombres dans l'ordre trié ascendant :

01  07 09 16 17 22 24 25 26 31

Comme vous le voyez probablement, nous pouvons trier des nombres de taille quelconque en réutilisant les paquets avec des tris sur des passes successives en commençant par le digit le plus à droite et en continuant vers les digits de gauche.

Voilà une illustration assez sympa du tri par base sur un terrain de sport. Dans cet exemple, les élèves font le tri de nombres à 3 digits et ils utilisent 9 paquets. D'abord ils se rangent dans le paquet ou la piste corespondant aux unités. Puis ils se regroupent dans l'ordre. Puis ils se rangent dans le paquet corespondant aux dizaines. Puis se regroupent dans l'ordre. Pareil pour le rangement sur les centaines. Ils se regroupent, et les nombres sont triés. (Notez qu'il n'y a pas de paquet pour '0' dans cet exemple. MAis il n'y a pas non plus de chiffre 0 dans les nombres, donc ça ne pose pas de problème.)

Synthèse

Pour faire une revue des différents algorithmes de tri expliqués ci-dessus, jetez un coup d'oeil à des animations sur chaque type de tri. Allez voir sur Vissualisation des algorithmes de tri ou sur Visualgo.

Auto-contrôle

En savoir plus ?

• Cette discussion sur le Tri par fusion contient une animation sympa.
• Une analyse accessible du Tri par base.
• Même le Président Obama connait le Tri à bulle :