Algorithmes

On a déjà réalisé quelques algorithmes dans les derniers chapitres. Pour illustrer les boucles for je vous montrais par exemple comment identifier le maximum d’une liste. Identifier le minimum suit donc le même principe.

On avait imaginé deux solutions au problème. La première consisterait à itérer sur tous les éléments de la liste, et à vérifier pour chaque élément qu’il est le minimum en le comparant avec les autres éléments.
S’il existe un autre élément plus petit, alors l’élément courant ne peut pas être le minimum.

numbers = [3, 2, 5, 8, 4, 7, 9, 1, 6]
minimum = numbers[0]

for i in numbers[1:]:
    is_minimum = True
    for j in numbers:
        if j < i:
            is_minimum = False
    if is_minimum:
        minimum = i

print('Le minimum est', minimum)

Cet algorithme fonctionne mais est particulièrement inefficace : il nous faut re-parcourir la liste complète pour chaque élément. Cela revient à dire que pour une liste de N éléments on va devoir effectuer un total de N² comparaisons.

L’autre algorithme que nous avions implémenté était bien meilleur. On pouvait simplement ne comparer chaque élément qu’avec les éléments précédents.
Et comme le minimum des éléments précédents est déjà connu à chaque instant, on peut juste comparer chaque élément avec le minimum déjà connu.

numbers = [3, 2, 5, 8, 4, 7, 9, 1, 6]
minimum = numbers[0]

for i in numbers[1:]:
    if i < minimum:
        minimum = i

print('Le minimum est', minimum)

En plus d’être plus efficace (on ne réalise ici que N comparaisons pour une liste de taille N), le code est bien plus concis est lisible.

Même si la différence de performances ne saute pas aux yeux, parce que nos listes sont de tailles modestes, cela peut devenir problématique quand on commence à beaucoup l’utiliser ou l’appliquer à des données en plus grande quantité.
Cette notion de nombre d’opérations effectuées en fonction du nombre d’éléments en entrée est ce que l’on appelle la complexité algorithmique¹.

On dit de notre premier algorithme qu’il a une complexité quadratique (N² opérations pour N éléments), et du second qu’il a une complexité linéaire (N opérations).

Maintenant que l’on sait identifier le plus petit élément d’une liste, on peut passer à un problème un peu plus compliqué, celui du tri d’une liste. C’est un problème algorithmique très classique qui consiste à ranger dans l’ordre les éléments d’une liste.

Une approche simple consiste à trouver le minimum pour le retirer de la liste et l’ajouter à une nouvelle liste d’éléments triés. L’opération est alors recommencée jusqu’à épuiser la liste de départ.
C’est ce qu’on appelle le tri par sélection.

numbers = [3, 2, 5, 8, 4, 7, 9, 1, 6]
sorted_numbers = []

while numbers:
    m = min(numbers)
    sorted_numbers.append(m)
    i = numbers.index(m)
    del numbers[i]

print(sorted_numbers)

Cet algorithme n’est pas le plus efficace puisqu’il effectue environ N² opérations (le calcul du minimum comptant comme N comparaisons) pour une liste de N éléments. Il faut savoir que d’autres algorithmes plus performants existent tels que le tri rapide et le tri fusion, mais qui sont hors de portée pour le moment.

Python implémente lui-même son propre algorithme de tri inspiré des tris précédents, le Tim sort (du nom de Tim Peters, contributeur de Python). Ce tri est accessible par la fonction sorted.

>>> numbers = [3, 2, 5, 8, 4, 7, 9, 1, 6]
>>> sorted(numbers)
[1, 2, 3, 4, 5, 6, 7, 8, 9]

Et si nous nous intéressions à des algorithmes un peu plus visuels ? Dans cette section je vous propose de dessiner diverses formes géométriques, à l’aide de caractères affichés dans le terminal.

Affichons un rectangle

Un premier exercice simple consiste à afficher un rectangle dans le terminal. À partir d’une largeur et d’une hauteur données (par exemple via des input()), on peut afficher les différents caractères pour dessiner les bords de notre rectangle.

On pourrait par exemple utiliser le caractère + pour les coins, - pour les lignes horizontales et | pour les lignes verticales.

Voici ce que donnerait un rectangle de dimensions 10×5 :

+--------+
|        |
|        |
|        |
+--------+

Et voici une solution possible pour cet exercice :

width = int(input('Entrez la largeur : '))
height = int(input('Entrez la hauteur : '))

for y in range(height):
    line = ''

    if y == 0 or y == height - 1:
        if width > 0:
            line += '+'
        line += '-' * (width - 2)
        if width > 1:
            line += '+'
    else:
        if width > 0:
            line += '|'
        line += ' ' * (width - 2)
        if width > 1:
            line += '|'

    print(line)

Passons au triangle

Augmentons un peu la difficulté et cherchons maintenant à afficher un triangle. Il s’agit d’un triangle équilatéral défini par sa hauteur. Voici par exemple un triangle de hauteur 10 :

         *
        * *
       *   *
      *     *
     *       *
    *         *
   *           *
  *             *
 *               *
*******************

Et comme vous le voyez, les lignes devront être centrées pour avoir un joli résultat.

Sans plus attendre, la solution :

height = int(input('Entrez la hauteur : '))

max_len = 2 * height - 1

width = 1

for y in range(height):
    padding = (max_len - width) // 2
    line = ' ' * padding

    if width > 2 and y != height - 1:
        line += '*' + ' ' * (width - 2) + '*'
    else:
        line += '*' * width

    print(line)
    width += 2

Mon beau sapin, roi des forêts

Encore un cran de difficulté supplémentaire, mais le code du précédent triangle va nous être bien utile. On voudrait ensuite faire dessiner un sapin à notre programme.

Un sapin serait composé de triangle et trapèzes empilés, ainsi qu’un rectangle pour le tronc. Il serait là encore défini par une hauteur, désignant le nombre de sections du sapin ainsi que la taille de son tronc.

Vous trouverez ci-dessous des exemples de sapins de différentes tailles.

   *
  ***
 *****
*******
   |

          *
         ***
        *****
       *******
        *****
       *******
      *********
     ***********
    *************
     ***********
    *************
   ***************
  *****************
 *******************
*********************
         |||
         |||
         |||

              *
             ***
            *****
           *******
            *****
           *******
          *********
         ***********
        *************
         ***********
        *************
       ***************
      *****************
     *******************
    *********************
      *****************
     *******************
    *********************
   ***********************
  *************************
 ***************************
*****************************
            |||||
            |||||
            |||||
            |||||

Je ne vous propose pas de solution pour cet exercice, mais sachez que vous pouvez le retrouver sur la plateforme HackInScience : Le sapin.