Trier un tableau
Ranger des valeurs dans l'ordre est un problème si important en informatique qu'il existe des dizaines d'algorithmes de tri ! On va en construire un pas à pas.
Échanger deux cases
Tous les tris reposent sur une opération de base : échanger deux éléments. Pour cela, il faut une variable temporaire, comme quand on échange le contenu de deux verres avec un troisième verre vide :
t est un tableau vaut [7, 2]
tampon est un nombre
tampon vaut t[0]
t[0] vaut t[1]
t[1] vaut tampon
affiche joindre(t, ', ') // 2, 7
Question : Que se passerait-il en écrivant seulement t[0] vaut t[1] puis t[1] vaut t[0] ? — Les deux cases vaudraient 2. Après t[0] vaut t[1], la valeur 7 est perdue : les deux cases contiennent 2. D'où la variable tampon.
Le tri par sélection
L'idée est simple, c'est celle qu'on utilise pour ranger des cartes :
- On cherche le plus petit élément du tableau, et on le met en première place.
- On cherche le plus petit parmi les suivants, et on le met en deuxième place.
- Et ainsi de suite jusqu'au bout.
procédure triSelection(liste)
n est un nombre vaut longueur(liste)
indiceMin est un nombre
tampon est un nombre
pour i de 0 à n - 2
// chercher le plus petit élément entre i et la fin
indiceMin vaut i
pour j de i + 1 à n - 1
si liste[j] < liste[indiceMin] alors
indiceMin vaut j
fin si
fin pour
// l'échanger avec l'élément à la place i
tampon vaut liste[i]
liste[i] vaut liste[indiceMin]
liste[indiceMin] vaut tampon
fin pour
fin procédure
valeurs est un tableau vaut [29, 4, 17, 8, 42, 1]
appelle triSelection(valeurs)
affiche joindre(valeurs, ', ') // 1, 4, 8, 17, 29, 42
La procédure modifie directement le tableau qu'on lui donne : pas besoin de le renvoyer.
Lance ce programme en pas à pas (F7) : tu verras indiceMin changer et les valeurs se déplacer dans le tableau à chaque échange.
Combien de comparaisons ?
Pour 6 éléments, la boucle intérieure fait 5 + 4 + 3 + 2 + 1 = 15 comparaisons. Pour 1 000 éléments, environ 500 000 ! Le tri par sélection est facile à comprendre, mais lent sur de grands tableaux. D'autres tris, plus malins (le tri fusion, le tri rapide), font beaucoup mieux.
Question : Pour trier du plus grand au plus petit avec ce même algorithme, que faut-il changer ? — Remplacer < par > dans la comparaison. En cherchant le plus grand au lieu du plus petit, on place les plus grandes valeurs en premier.
Dans la vraie vie
Dans tes programmes, tu peux simplement utiliser la fonction trier(tableau) de CoddyRun. Mais maintenant, tu sais ce qui se passe à l'intérieur !
En résumé
- Échanger deux cases demande une variable temporaire (
tampon). - Tri par sélection : chercher le plus petit des éléments restants et le placer au bon endroit.
- Un algorithme se juge aussi à sa rapidité : le nombre d'opérations compte.
trier(tableau) fait le travail pour toi dans tes programmes.
