Min/Max d'un tableau

Introduction

L'objectif de cette leçon est d'apprendre à trouver la valeur minimale et la valeur maximale dans un tableau.

Savoir identifier les extrêmes dans un ensemble de données est une opération courante : pensez à trouver la note la plus haute et la plus basse dans une classe, le produit le moins cher et le plus cher dans un catalogue, ou le jour le plus froid et le plus chaud du mois à partir de relevés de température.

La méthode que nous allons découvrir est un classique de l'algorithmique. Comme pour le calcul de la somme, elle repose sur un parcours complet du tableau, mais la logique à l'intérieur de la boucle sera différente. Au lieu d'accumuler, nous allons comparer et mettre à jour.

1. La logique de la recherche d'un extrêmum

Imaginons que vous ayez une liste de nombres sur une feuille de papier et que vous deviez trouver le plus grand. Comment feriez-vous intuitivement ?

Vous liriez probablement le premier nombre et le garderiez en tête comme étant "le plus grand pour l'instant". Ensuite, vous liriez le deuxième nombre. S'il est plus grand que celui que vous avez en tête, vous l'oubliez et mémorisez ce nouveau nombre. Sinon, vous continuez avec le nombre que vous aviez déjà. Vous répétez ce processus jusqu'à la fin de la liste.

L'algorithme pour trouver le maximum (ou le minimum) fonctionne exactement de la même manière.

La stratégie est la suivante :

1. Initialisation (l'hypothèse de départ) : On suppose que le premier élément du tableau est le maximum. On stocke cette valeur dans une variable, par exemple valeur_max.

   • Pourquoi le premier élément ? C'est la méthode la plus sûre. Si on initialisait valeur_max à 0, par exemple, l'algorithme échouerait si toutes les valeurs du tableau sont négatives (ex: [-10, -5, -2]). En prenant le premier élément, on est sûr de partir avec une valeur qui existe réellement dans le tableau.

2. Parcours et comparaison : On parcourt le reste du tableau, du deuxième élément jusqu'à la fin.

3. Mise à jour : Pour chaque élément rencontré, on le compare à notre valeur_max actuelle.

   • Si l'élément est plus grand que valeur_max, alors notre hypothèse de départ était fausse. Cet élément devient le nouveau maximum. On met donc valeur_max à jour avec la valeur de cet élément.
   • Sinon, on ne fait rien et on passe à l'élément suivant.

4. Résultat : Une fois la boucle terminée, la variable valeur_max contient nécessairement la plus grande valeur de tout le tableau.

La logique pour trouver le minimum est identique, il suffit d'inverser la comparaison (< au lieu de >).

2. Algorithme pour trouver le Minimum et le Maximum

Il est très efficace de chercher le minimum et le maximum en même temps, en un seul parcours de tableau.

L'algorithme est une simple extension de la logique précédente :

Algorithme TrouverMinMax
Variables
  Tableau T[...] : Entier // ou Reel
  valeur_min : Entier
  valeur_max : Entier
  i : Entier
  N : Entier // Taille du tableau

Début
  // On suppose que le tableau T est rempli et que N > 0.

  // 1. Initialisation
  valeur_min ← T[0]
  valeur_max ← T[0]

  // 2. Parcours à partir du DEUXIÈME élément
  Pour i allant de 1 à N - 1 Faire
    // 3. Mise à jour du maximum
    Si T[i] > valeur_max Alors
      valeur_max ← T[i]
    // 4. Mise à jour du minimum
    Sinon Si T[i] < valeur_min Alors
      valeur_min ← T[i]
    FinSi
  FinPour

  // 5. Affichage des résultats
  Ecrire("La valeur minimale est : ", valeur_min)
  Ecrire("La valeur maximale est : ", valeur_max)
Fin

Note sur l'efficacité : remarquez l'utilisation de Sinon Si. C'est une petite optimisation. Si un nombre est plus grand que le maximum actuel (valeur_max), il ne peut pas être plus petit que le minimum actuel (valeur_min), donc il est inutile de faire la deuxième comparaison. Cela rejoint votre objectif d'écrire du code performant !

Pour une description très claire de cette méthode, vous pouvez consulter la ressource suivante. Bien qu'elle soit en anglais, le pseudo-code est universel et illustre parfaitement notre algorithme.

3. Analyse d'un exemple en français

Voyons maintenant un exemple concret dans un document d'exercices. L'algorithme est légèrement différent mais la logique de base reste la même.

En analysant l'algorithme MinMax du document, vous remarquerez deux choses :

1. L'indexation du tableau commence à 1 (T[1]), ce qui est une convention possible. Nous continuerons à utiliser l'indexation à partir de 0, plus courante en Java.
2. L'initialisation se fait bien avec Min←T[1] et Max←T[1]. Cependant, la boucle de traitement Pour I←1 à N Faire inclut le premier élément, qui est comparé à lui-même. C'est une petite redondance. Un algorithme légèrement plus optimisé commencerait la boucle au deuxième élément, comme nous l'avons fait dans notre pseudo-code.

4. À vous de jouer !

Votre goût pour la pratique va être satisfait ! Voici un problème à résoudre.

Problème :
Un capteur a enregistré les températures (en degrés Celsius) à chaque heure pendant 10 heures. Ces températures sont stockées dans un tableau.

Écrivez un algorithme nommé AnalyseTemperatures qui :

1. Déclare un tableau Temperatures de 10 nombres réels. Vous pouvez imaginer qu'il est pré-rempli avec les valeurs : [12.5, 13.0, 11.8, 11.5, 12.0, 14.2, 15.1, 14.8, 13.5, 12.9].
2. Trouve la température la plus basse enregistrée.
3. Trouve la température la plus haute enregistrée.
4. Affiche ces deux températures avec un message clair.

Prenez le temps de rédiger l'algorithme sur papier en appliquant la logique que nous avons étudiée.

Algorithme AnalyseTemperatures
Variables
  Tableau Temperatures[10] : Reel // Supposons rempli avec [12.5, 13.0, 11.8, 11.5, 12.0, 14.2, 15.1, 14.8, 13.5, 12.9]
  temp_min : Reel
  temp_max : Reel
  i : Entier

Début
  // On considère que le tableau n'est pas vide.
  
  // Initialisation avec le premier élément
  temp_min ← Temperatures[0]
  temp_max ← Temperatures[0]

  // Parcours du reste du tableau (de l'index 1 à 9)
  Pour i allant de 1 à 9 Faire
    Si Temperatures[i] > temp_max Alors
      temp_max ← Temperatures[i]
    Sinon Si Temperatures[i] < temp_min Alors
      temp_min ← Temperatures[i]
    FinSi
  FinPour

  // Affichage des résultats
  Ecrire("La température la plus haute enregistrée est : ", temp_max, "°C")
  Ecrire("La température la plus basse enregistrée est : ", temp_min, "°C")
Fin

Conclusion

Félicitations ! Vous maîtrisez maintenant un autre algorithme de parcours de tableau essentiel. Cette méthode pour trouver le minimum et le maximum est un pilier que vous retrouverez partout.

Les points clés à retenir sont :

• La stratégie consiste à poser une hypothèse (le premier élément est le min/max) et à la challenger en parcourant le reste des données.
• L'initialisation des variables min et max avec le premier élément du tableau est la technique la plus robuste.
• Le parcours peut se faire en une seule boucle pour trouver les deux extrêmes simultanément.
• De petites optimisations, comme utiliser Sinon Si, peuvent rendre l'algorithme plus performant.

Et après ?

Nous avons exploré le traitement des tableaux de nombres. Mais un tableau peut aussi contenir d'autres types de données, comme des caractères. Dans la prochaine leçon, nous verrons comment manipuler une chaîne de caractères comme un tableau de caractères, ce qui nous ouvrira la porte à de nombreux nouveaux problèmes intéressants, comme compter les voyelles dans un mot ou vérifier si un texte est un palindrome.