On veut donc trier un tableau ou pour nous une liste qu’on nomme ici t.

t = [8, 6, 2, 9, 3, 4]

Questions 1 :

• Que vaut len(t) ?
• Que vaut t[0] ? t[1] ?
• Que vaut t[5] ? t[6] ?
• Que vaut t[-1] ?

Réponses 1 :

Question 2 :

• Comment trouver l’indice du minimum de cette liste ?

t = [8, 6, 2, 9, 3, 4]

Réponse 2 :

En code, qu’est-ce que ça donne ?

def indice_minimum(liste):
    assert len(liste) > 0
    i_min = ...
    for i in range(..., ......):
        if liste[...] < liste[...]:
            i_min = ...
    return ...

Question 3 :

• Compléter le code ci-dessus.
  Pour le tester :

  >>> t = [8, 6, 2, 9, 3, 4]
  >>> indice_minimum(t)
  2
  >>>

Réponse 3 :

Question 4 :

• Comment intervertir les valeurs de deux variables a et b en python ?

Réponse 4 :

• En python, c’est plus facile que dans d’autres languages :

  >>> a = 42
  >>> b = 21
  >>> a, b
  (42, 21)
  >>> a, b = b, a # interversion
  >>> a, b
  (21, 42)
  >>> a
  21
  >>> b
  42
  >>>  # c'est gagné 🙂

Le tri en lui même

Reprenons maintenant notre tri, comme sur la vidéo. Les étapes sont :

[8, 6, 2, 9, 3, 4]
indice du minimum : 2
On intervertit les valeurs des rangs 0 et 2
[2, 6, 8, 9, 3, 4]
indice du minimum : 4
On intervertit les valeurs des rangs 1 et 4
[2, 3, 8, 9, 6, 4]
indice du minimum : 5
On intervertit les valeurs des rangs 2 et 5
[2, 3, 4, 9, 6, 8]
indice du minimum : 4
On intervertit les valeurs des rangs 3 et 4
[2, 3, 4, 6, 9, 8]
indice du minimum : 5
On intervertit les valeurs des rangs 4 et 5
[2, 3, 4, 6, 8, 9]
>>> 

On a donc deux boucles imbriquées (je proposerai un corrigé avec deux fonctions pour éviter cette lourdeur) :

• une boucle « extérieure » avec une indice rang qui parcourt la liste t an allant des rangs 0 à 4 ici, donc de 0 à len(t) - 2 en règle générale,
  • une boucle « intérieure » avec un indice i qui cherche l’indice du minimum i_min,
  • on intervertit alors t[rang] et t[i_min] après cette boucle « intérieure ».

En pseudo-code, l’algorithme du tri par sélection est (source Wikipedia) :

  procédure tri_selection(liste t)
      pour rang de 0 à len(t) - 2
          i_min ← rang       
          pour i de rang + 1 à len(t) - 1
              si t[i] < t[i_min], alors i_min ← i
          fin pour
          si i_min ≠ rang, alors échanger t[rang] et t[i_min]
      fin pour
  fin procédure

Mieux comprendre le rôle des indices ? Une nouvelle vidéo :

Question 5 pour vendredi :

• programmer une fonction tri_selection(t) qui effectue ce tri.
• déposer ce code dans la collecte prévue à cet effet sur mon bureau numérique.

Réponse 5, finalement samedi – CORRIGÉ :

Déception : seulement huit neuf codes rendus, mais aussi des satisfactions !
J’ai commenté individuellement sur MBN.

Version 1 – deux boucles imbriquées :

def tri_selection(t):
    # il faut une liste non vide
    assert len(t) > 0
    print(t)
    # parcours de la liste jusqu'à l'avant dernier
    for rang in range(len(t) - 1):
        # recherche de l'indice du minimum
        # on initialise
        i_min = rang
        # on parcourt le reste de la liste
        for i in range(rang + 1, len(t)):
            # si on trouve plus petit ...
            if t[i] < t[i_min]:
                # ... alors l'indice change !
                i_min = i
        print("indice du minimum :", i_min)

        if i_min != rang :
            # interversion : le minimum passe devant
            print("On intervertit les valeurs des rangs", rang, "et", i_min)
            t[rang], t[i_min] = t[i_min], t[rang]
        print(t)

t = [8, 6, 2, 9, 3, 4]
tri_selection(t)

Version 2 – en utilisant la fonction indice_minimum :

def indice_minimum(liste, rang):
    # il faut une liste non vide
    assert len(liste) > 0
    # on initialise
    i_min = rang
    # on parcourt le reste de la liste
    for i in range(rang + 1, len(liste)):
        # si on trouve plus petit ...
        if liste[i] < liste[i_min]:
            # ... alors l'indice change !
            i_min = i
    # On renvoie l'indice du minimum
    return i_min

def tri_selection(t):
    print(t)
    # parcours de la liste jusqu'à l'avant dernier
    for rang in range(len(t) - 1):
        # recherche de l'indice du minimum
        ind_min = indice_minimum(t, rang)
        print("indice du minimum :", ind_min)
        if ind_min != rang :
            # interversion : le minimum passe devant
            print("On intervertit les valeurs des rangs", rang, "et", ind_min)
            t[rang], t[ind_min] = t[ind_min], t[rang]
        print(t)

t = [8, 6, 2, 9, 3, 4]
tri_selection(t)

Besoin d’un autre regard ?

Suite de notre progression en NSI ?

• Corrigé et autre algorithme de tri vendredi.
• Salon de discussion discord lundi prochain le 23 mars à 11h00.

Bon courage !