Algorithmes avancés

a. 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...