Tri par sélection

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 !

6 réflexions au sujet de « Tri par sélection »

  1. Bonjour !

    Je n’ai pas compris un petit détail dans le pseudo-code de Wikipédia (ligne 4) :
    pour i de rang + 1 à len(t) – 1

    Pourquoi « len(t) -1 » ? Celui-ci n’est-t’il pas exclu ? J’ai essayé avec ce len(t) – 1 mais cela ne triait pas t[5] (qui est ici égal à 4). En revanche, avec len(t), mon code fonctionne. Je ne comprends pas pourquoi…

    (j’ai cette même interrogation à la ligne 2 « pour rang de 0 à len(t) – 2 » où je ne comprends pas pourquoi « – 2 » et non « – 1 »)

    Merci de vos réponses 🙂

N'hésitez-pas à poser une question, ou faire avancer le schmilblick

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l’aide de votre compte WordPress.com. Déconnexion /  Changer )

Photo Google

Vous commentez à l’aide de votre compte Google. Déconnexion /  Changer )

Image Twitter

Vous commentez à l’aide de votre compte Twitter. Déconnexion /  Changer )

Photo Facebook

Vous commentez à l’aide de votre compte Facebook. Déconnexion /  Changer )

Connexion à %s

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur la façon dont les données de vos commentaires sont traitées.