Algorithmes avancés
1. Les algorithmes des tris
a. Le principe
Vous avez pu voir dans les exemples précédents l’intérêt des tableaux pour le stockage de valeurs multiples. Mais
suivant le cas il peut être utile d’avoir besoin d’obtenir une liste ordonnée de valeurs par ordre croissant ou
décroissant. Autrement dit vous voulez trier le contenu du tableau. Prenez le cas d’un professeur souhaitant trier les
notes de ses élèves de la plus basse à la plus haute, ou des résultats d’un tirage du loto pour le rendre plus lisible.
Imaginez un tirage du loto de cinq numéros, évidemment tous différents, dont les valeurs s’étalent entre 1 et 49. Voici
l’état initial du tableau suite au tirage au sort :
Il existe plusieurs méthodes permettant de trier ces différentes valeurs. Elles ont toutes leurs qualités et leurs
défauts. Ainsi une méthode sera lente, l’autre sera plus gourmande en mémoire, et ainsi de suite. C’est leur
complexité qui détermine leur usage notamment pour de grandes plages de valeurs.
Dans les algorithmes suivants, la variable Cpt contient le nombre d’éléments du tableau initial et t[] est le tableau.
Il est intéressant de prendre en compte la complexité de ces divers algorithmes, bien que cette notion, présentée au
premier chapitre, ne soit généralement pas (ou peu) abordée dans les premières années d’études en informatique.
Les algorithmes ont souvent une complexité proche. Pourtant à l’usage un tri shell est plus rapide qu’un tri par
sélection, tout dépendant du nombre d’éléments et l’éventuel ordre de ceuxci au départ.
b. Le tri par création
Le tri par création ne sera abordé que du point de vue théorique. En effet si cette méthode semble simple, elle est en
fait lourde et compliquée. Si on demande à un débutant en programmation comment trier un tableau, il vous
proposera très certainement de créer un deuxième tableau dans lequel on placera au fur et à mesure les éléments du
premier tableau dans l’ordre croissant.
C’est une très mauvaise idée pour de multiples raisons dont :
q L’ajout d’un second tableau double la mémoire nécessaire.
q La recherche du plus petit élément est plus compliquée qu’on ne le pense car à chaque passage, il ne faut pas
reprendre ceux déjà sortis, et c’est compliqué.
q Le nombre de boucles et de recherches est important. La complexité de l’algorithme résultant aussi,
supérieure aux autres.
q Pour toutes ces raisons le tri par création ne doit absolument pas être utilisé.
c. Le tri par sélection
Le tri par sélection est très simple : il consiste à sélectionner dans le tableau la plus petite valeur et la permuter avec
le premier élément du tableau, puis la deuxième plus petite valeur (hors premier élément) et à la permuter avec le
deuxième élément du tableau, et ainsi de suite, et cela pour tous les éléments du tableau. Voici les étapes
nécessaires depuis l’exemple cidessus :
q Étape 1 : la plus petite valeur est 9, on permute 9 et 48.
q Étape 2 : la plus petite valeur suivante est 17, déjà à la bonne position, on passe à la suivante.
48
17
25
9
34
9
17
25
48
34
- 1 -
© ENI Editions - All rigths reserved - Jonifar lina
108
1. Les algorithmes des tris
a. Le principe
Vous avez pu voir dans les exemples précédents l’intérêt des tableaux pour le stockage de valeurs multiples. Mais
suivant le cas il peut être utile d’avoir besoin d’obtenir une liste ordonnée de valeurs par ordre croissant ou
décroissant. Autrement dit vous voulez trier le contenu du tableau. Prenez le cas d’un professeur souhaitant trier les
notes de ses élèves de la plus basse à la plus haute, ou des résultats d’un tirage du loto pour le rendre plus lisible.
Imaginez un tirage du loto de cinq numéros, évidemment tous différents, dont les valeurs s’étalent entre 1 et 49. Voici
l’état initial du tableau suite au tirage au sort :
Il existe plusieurs méthodes permettant de trier ces différentes valeurs. Elles ont toutes leurs qualités et leurs
défauts. Ainsi une méthode sera lente, l’autre sera plus gourmande en mémoire, et ainsi de suite. C’est leur
complexité qui détermine leur usage notamment pour de grandes plages de valeurs.
Dans les algorithmes suivants, la variable Cpt contient le nombre d’éléments du tableau initial et t[] est le tableau.
Il est intéressant de prendre en compte la complexité de ces divers algorithmes, bien que cette notion, présentée au
premier chapitre, ne soit généralement pas (ou peu) abordée dans les premières années d’études en informatique.
Les algorithmes ont souvent une complexité proche. Pourtant à l’usage un tri shell est plus rapide qu’un tri par
sélection, tout dépendant du nombre d’éléments et l’éventuel ordre de ceuxci au départ.
b. Le tri par création
Le tri par création ne sera abordé que du point de vue théorique. En effet si cette méthode semble simple, elle est en
fait lourde et compliquée. Si on demande à un débutant en programmation comment trier un tableau, il vous
proposera très certainement de créer un deuxième tableau dans lequel on placera au fur et à mesure les éléments du
premier tableau dans l’ordre croissant.
C’est une très mauvaise idée pour de multiples raisons dont :
q L’ajout d’un second tableau double la mémoire nécessaire.
q La recherche du plus petit élément est plus compliquée qu’on ne le pense car à chaque passage, il ne faut pas
reprendre ceux déjà sortis, et c’est compliqué.
q Le nombre de boucles et de recherches est important. La complexité de l’algorithme résultant aussi,
supérieure aux autres.
q Pour toutes ces raisons le tri par création ne doit absolument pas être utilisé.
c. Le tri par sélection
Le tri par sélection est très simple : il consiste à sélectionner dans le tableau la plus petite valeur et la permuter avec
le premier élément du tableau, puis la deuxième plus petite valeur (hors premier élément) et à la permuter avec le
deuxième élément du tableau, et ainsi de suite, et cela pour tous les éléments du tableau. Voici les étapes
nécessaires depuis l’exemple cidessus :
q Étape 1 : la plus petite valeur est 9, on permute 9 et 48.
q Étape 2 : la plus petite valeur suivante est 17, déjà à la bonne position, on passe à la suivante.
48
17
25
9
34
9
17
25
48
34
- 1 -
© ENI Editions - All rigths reserved - Jonifar lina
108