Une fois n’est pas coutume, ce chapitre n’a pas pour but de présenter un nouveau type de données, un nouveau jeu d’instructions, ou que sais-je encore.
Son propos est de détailler quelques techniques de programmation qui possèdent deux grands points communs :
leur connaissance est parfaitement indispensable
elles sont un rien finaudes
Et que valent quelques kilos d’aspirine, comparés à l’ineffable bonheur procuré par la compréhension suprême des arcanes de l’algorithmique ? Hein ?
1. Tri d’un tableau : le tri par SELECtion
Première de ces ruses de sioux, et par ailleurs tarte à la crème absolue du programmeur, donc : le tri de tableau.
Combien de fois au cours d’une carrière (brillante) de développeur a-t-on besoin de ranger des valeurs dans un ordre donné ? C’est inimaginable. Aussi, plutôt qu’avoir à réinventer à chaque fois la roue, le fusil à tirer dans les coins, le fil à couper le roquefort et la poudre à maquiller, vaut-il mieux avoir assimilé une ou deux techniques solidement éprouvées, même si elles paraissent un peu ardues au départ.
Il existe plusieurs stratégies possibles pour trier les éléments d’un tableau ; nous en verrons deux : le tri par sélection, et le tri à bulles. Champagne !
Commençons par le tri par sélection.
Admettons que le but de la manœuvre soit de trier un tableau de 12 éléments dans l’ordre croissant. La technique du tri par sélection est la suivante : on met en bonne position l’élément numéro 1, c’est-à-dire le plus petit. Puis en met en bonne position l’élément suivant. Et ainsi de suite jusqu’au dernier. Par exemple, si l’on part de :
45 122 12 3 21 78 64 53 89 28 84 46
On commence par rechercher, parmi les 12 valeurs, quel est le plus petit élément , et où il se trouve. On l’identifie en quatrième position (c’est le nombre 3), et on l’échange alors avec le premier élément (le nombre 45). Le tableau devient ainsi :
3 122 12 45 21 78 64 53 89 28 84 46
On recommence à chercher le plus petit élément, mais cette fois, seulement à partir du deuxième (puisque le premier est maintenant correct, on n’y touche plus). On le trouve en troisième position (c’est le nombre 12). On échange donc le deuxième avec le troisième :
3 12 122 45 21 78 64 53 89 28 84 46
On recommence à chercher le plus petit élément à partir du troisième (puisque les deux premiers sont maintenant bien placés), et on le place correctement, en l’échangeant, ce qui donnera in fine :
3 12 21 45 122 78 64 53 89 28 84 46
Et cetera, et cetera, jusqu’à l’avant dernier.
En bon français, nous pourrions décrire le processus de la manière suivante :
Boucle principale : prenons comme point de départ le premier élément, puis le second, etc, jusqu’à l’avant dernier.
Boucle secondaire : à partir de ce point de départ mouvant, recherchons jusqu’à la fin du tableau quel et le plus petit élément. Une fois que nous l’avons trouvé, nous l’échangeons avec le point de départ.
Cela s’écrit :
boucle principale : le point de départ se décale à chaque tour
Pour i ← 0 à 10
on considère provisoirement que t(i) est le plus petit élément
posmini ← i
on examine tous les éléments suivants
Pour j ← i + 1 à 11
Si t(j) < t(posmini) Alors
posmini ← j
Finsi
j suivant
A cet endroit, on sait maintenant où est le plus petit élément. Il ne reste plus qu'à effectuer la permutation.
temp ← t(posmini)
t(posmini) ← t(i)
t(i) ← temp
On a placé correctement l'élément numéro i, on passe à présent au suivant.
i suivant
Mer 13 Fév - 9:47