Aller au contenu

TP - Mise en oeuvre du tri

C'est désormais à vous de jouer pour coder les fonctions de tri par sélection et de tri par insertion en Python !

Exercice 1 : Tri par sélection

Pour obtenir un rappel du tri par sélection, consultez la page de cours dédiée.

Question 1 : Fonction echange()

Écrire une fonction echange(l, i, j) qui inverse les valeurs d'indice i et j dans la liste l, et qui ne renvoie rien.

Par exemple, si on échange de place les valeurs aux indices 2 et 4 de la liste [7, 2, 1, 9, 3, 2], alors notre liste sera modifiée et elle vaudra désormais [7, 2, 3, 9, 1, 2].

def echange(l, i, j):
    """
    Modifie la liste donnée en inversant les valeurs d'indices donnés
    Entrées : l - list : liste à modifier
              i - int : premier indice
              j - int : deuxième indice
    Sortie : None
    """


ma_liste = [1, 2, 3, 4]
echange(ma_liste, 2, 1)
print(ma_liste)  # Doit afficher [1, 3, 2, 4]
Qui ne renvoie rien ?

Comme les listes sont mutables, on peut les modifier sans changer leur adresse. Ainsi, le code ci-dessous montre comment fonctionne ce phénomène.

def modifier_liste(liste):
    liste[0] = 4
    # Et on ne renvoie rien (pas de return).

ma_liste = [2, 8, 3]
print(ma_liste)

# Même si l'argument (ma_liste) n'a pas le même que le paramètre de la fonction (liste),
# notre liste sera quand même modifiée.
resultat = modifier_liste(ma_liste)

print(resultat) # Affiche None car on n'a rien renvoyé.
print(ma_liste) # Affiche [4, 8, 3] ce qui prouve que notre liste a bien été modifiée.
Comment faire ?

Pour y arriver, il sera nécessaire d'utiliser au moins une variable temporaire. Le plus simple est de stocker les valeurs à échanger dans des variables distinctes. Ensuite, il ne restera plus qu'à les affecter à leur nouvel emplacement dans les listes.

Solution 
def echange(l, i, j):
    """
    Modifie la liste donnée en inversant les valeurs d'indices donnés
    Entrées : l - list : liste à modifier
              i - int : premier indice
              j - int : deuxième indice
    Sortie : None
    """
    # Enregistrer dans une variable la valeur de l[i]
    valeur_i = l[i]
    # Enregistrer dans une variable la valeur de l[j]
    valeur_j = l[j]
    # Affecter dans l[i] la valeur de l[j] depuis la variable
    l[i] = valeur_j
    # Affecter dans l[j] la valeur de l[i] depuis la variable
    l[j] = valeur_i


ma_liste = [1, 2, 3, 4]
echange(ma_liste, 2, 1)
print(ma_liste)  # Affiche [1, 3, 2, 4]

Question 2 : Fonction indice_min()

Écrire une fonction indice_min(l, debut) qui renvoie l'indice de la valeur minimale dans l à partir de l'indice debut.

Par exemple, dans la liste [1, 8, 3, 7, 5], si on cherche à partir de l'indice 1, on trouve 3 comme étant la valeur minimale. On renvoie alors 2, l'indice de la valeur 3.

def indice_min(l, debut):
    """
    Renvoie l'indice de la valeur minimale dans l[debut:]
    Entrées : l - list : Liste où chercher
              debut - int : Indice du début de la recherche (inclus)
    Sortie : int : Indice de la valeur minimale
    >>> indice_min([1, 8, 3, 7, 5], 1)
    2
    """
Une piste ?

On est ici face à un problème de recherche du minimum, et de son indice. On va donc devoir stocker ces deux valeurs dans des variables, puis consulter toutes les valeurs de la liste, et mettre à jour en conséquence.

Comment initialiser mon problème ?

Au début, on peut initialiser la valeur minimale à l[debut] et l'indice de la valeur minimale à debut. Il ne restera plus qu'à parcourir notre liste entre les indices debut+1 et len(l) exclu, et mettre à jour ces deux variables lorsqu'une valeur plus petite est trouvée.

Solution 
def indice_min(l, debut):
    """
    Renvoie l'indice de la valeur minimale dans l[debut:]
    Entrées : l - list : Liste où chercher
              debut - int : Indice du début de la recherche (inclus)
    Sortie : int : Indice de la valeur minimale
    >>> indice_min([1, 8, 3, 7, 5], 1)
    2
    """
    # Sauvegarder dans deux variables (qui serviront à
    # stocker la valeur minimale et son indice) les valeurs
    # initiales l[debut] et debut respectivement.
    valeur_minimale = l[debut]
    indice_minimal = debut

    # Parcourir toutes les valeurs de l[debut] à la fin de l
    for i in range(debut, len(l)):
        # Si la valeur courante est plus petite que la
        # valeur minimale enregistrée, mettre à jour la
        # valeur et son indice.
        if l[i] < valeur_minimale:
            valeur_minimale = l[i]
            indice_minimal = i

    # Renvoyer l'indice de la valeur minimale
    return indice_minimal

Question 3 : Fonction finale tri_selection()

Écrire une fonction tri_selection(l) qui trie la liste l et qui ne renvoie rien. La fonction appliquera l'algorithme du tri par sélection en utilisant les deux dernières fonctions codées.

def tri_selection(l):
    """
    Trie la liste l par ordre croissant selon l'algorithme du tri par sélection.
    Entrées : l - list : Liste à trier
    Sorties : None
    """


ma_liste = [3, 7, 2, 8, 1]
tri_selection(ma_liste)
print(ma_liste)  # Doit afficher [1, 2, 3, 7, 8]
Algorithme du tri par sélection

L'algorithme du tri par sélection consiste à trier petit à petit la liste en sélectionnant la valeur la plus petite (pas encore triée) et en l'ajoutant après les valeurs déjà triées. Cette séparation se fait naturellement avec une boucle FOR.

Je suis perdu

Appliquez l'algorithme pas à pas sur une feuille. Vous pouvez vous aider de ce site en sélectionnant SEL pour visualiser pas à pas l'algorithme.

Essayez de remarquer les étapes récurrentes, et les deux fonctions codées précedemment. Cela vous aidera à construire la boucle nécessaire dans l'algorithme.

Solution 
def tri_selection(l):
    """
    Trie la liste l par ordre croissant selon l'algorithme du tri par sélection.
    Entrées : l - list : Liste à trier
    Sorties : None
    """
    # L'indice i correspond à la séparation entre la partie triée et la partie non triée de la liste.
    for i in range(len(l)):
        # On cherche l'indice de la valeur minimale parmi les valeurs non triées
        indice = indice_min(l, i)
        # On échange de place avec la première valeur non triée (qui est d'indice i).
        echange(l, i, indice)


ma_liste = [3, 7, 2, 8, 1]
tri_selection(ma_liste)
print(ma_liste)  # Affiche [1, 2, 3, 7, 8]

Exercice 2 : Tri par insertion

Pour obtenir un rappel du tri par sélection, consultez la page de cours dédiée.

Question 1 : Fonction deplacer()

Écrire une fonction deplacer(l, dest, source) qui déplace la valeur d'indice source à la position dest , et qui ne renvoie rien.

Par exemple, si on déplace la valeur à l'indice 3 vers l'indice 1 dans la liste [7, 5, 2, 9, 1], alors notre liste sera modifiée et elle vaudra désormais [7, 9, 5, 2, 1].

def deplacer(l, dest, source):
    """
    Modifie la liste donnée en déplacant une valeur d'indice donnée vers une position donnée.
    Entrées : l - list : liste à modifier
              dest - int : indice où insérer la valeur (l'insertion se fait entre dest-1 et dest)
              source - int : indice de la valeur à déplacer.
    Sortie : None
    """


ma_liste = [1, 2, 3, 4, 5]
deplacer(ma_liste, 1, 3)
print(ma_liste)  # Doit afficher [1, 4, 2, 3, 5]
Déplacer ? Comment fais-je ?

Pour déplacer une valeur, il y a plusieurs possibilités :

  • On peut déplacer les valeurs une par une vers la droite, afin de libérer un espace pour écrire la valeur à déplacer vers la gauche.
  • On peut supprimer la valeur à déplacer, puis l'insérer à sa nouvelle position grâce aux méthodes déjà existantes en Python. C'est cette méthode qu'on va privilégier.
Quels outils Python me propose ?

Avec les listes, on peut supprimer un élément avec ma_liste.pop(indice). Cette méthode renvoie la valeur de l'élément supprimé.

On peut aussi insérer un élément grâce à ma_liste.insert(indice, valeur).

Solution 
def deplacer(l, dest, source):
    """
    Modifie la liste donnée en déplacant une valeur d'indice donnée vers une position donnée.
    Entrées : l - list : liste à modifier
    dest - int : indice où insérer la valeur (l'insertion se fait entre dest-1 et dest)
    source - int : indice de la valeur à déplacer.
    Sortie : None
    """
    valeur = l[source]
    l.pop(source)  # On peut aussi écrire directement valeur = l.pop(source)
    l.insert(dest, valeur)

ma_liste = [1, 2, 3, 4, 5]
deplacer(ma_liste, 1, 3)
print(ma_liste)  # Affiche [1, 4, 2, 3, 5]

Question 2 : Fonction position_tri()

Écrire une fonction position_tri(l, fin, valeur) qui renvoie l'indice où insérer la valeur valeur dans la sous-liste l[:fin] allant de 0 à fin exclu, tout en gardant cette sous-liste triée. On suppose que cette sous-liste est bien triée par ordre croissant. Attention, cette fonction n'insère pas la valeur dans la liste !

Par exemple, pour insérer 5 dans la liste [1, 3, 4, 6, 2, 8, 3, 9] en se limitant à la sous-liste allant jusqu'à l'indice 4 exclu, il faudra insérer 5 entre les valeurs 4 et 6. On renvoie donc l'indice de 6 qui est 3.

def position_tri(l, fin, valeur):
    """
    Renvoie l'indice où insérer une valeur dans la sous-liste l[:fin] en conservant le tri.
    Entrées : l - list : Liste où chercher
              fin - int : Indice de fin de la sous-liste (exclu)
              valeur - ??? : Valeur qu'on souhaite insérer (mais qu'on n'insère pas)
    Sortie : int : Indice où insérer la valeur
    >>> position_tri([1, 3, 4, 5, 2, 9, 4, 1], 4, 2)
    1
    """
Une piste ?

Le plus dur est de comprendre ce que fait la fonction. Essayez-la sur différentes listes pour vérifier que vous avez compris ce que l'on attend de vous.

Comment je cherche ?

Il va falloir regarder toutes les valeurs de l[:fin] dans l'ordre croissant jusqu'à trouver une valeur supérieure à la valeur à insérer. Il ne restera plus qu'à renvoyer son indice.

Solution 
def position_tri(l, fin, valeur):
    """
    Renvoie l'indice où insérer une valeur dans la sous-liste l[:fin] en conservant le tri.
    Entrées : l - list : Liste où chercher
    fin - int : Indice de fin de la sous-liste (exclu)
    valeur - ??? : Valeur qu'on souhaite insérer (mais qu'on n'insère pas)
    Sortie : int : Indice où insérer la valeur
    >>> position_tri([1, 3, 4, 5, 2, 9, 4, 1], 4, 2)
    1
    """
    # On regarde toutes les valeurs entre 0 et fin exclu
    for i in range(fin):
        # Si on dépasse la valeur qu'on souhaite insérer, on doit renvoyer l'indice courant car
        # c'est ici qu'en insérant notre valeur, le tri sera conservé.
        if valeur < l[i]:
            return i
    # Si aucun résultat n'est trouvé, on renvoie l'indice de fin, ce qui signifie que la valeur devra
    # être insérée après toutes les autres.
    return fin

Question 3 : Fonction finale tri_insertion()

Écrire une fonction tri_insertion(l) qui trie la liste l et qui ne renvoie rien. La fonction appliquera l'algorithme du tri par insertion en utilisant les deux dernières fonctions codées.

def tri_insertion(l):
    """
    Trie la liste l par ordre croissant selon l'algorithme du tri par insertion.
    Entrées : l - list : Liste à trier
    Sorties : None
    """


ma_liste = [3, 7, 2, 8, 1]
tri_selection(ma_liste)
print(ma_liste)  # Doit afficher [1, 2, 3, 7, 8]
Algorithme du tri par insertion

L'algorithme du tri par sélection consiste à trier petit à petit la liste en insérant une valeur pas encore triée dans la zone des valeurs triées. Ces insertions successives se font naturellement avec une boucle FOR.

Je suis perdu

Appliquez l'algorithme pas à pas sur une feuille. Vous pouvez vous aider de ce site en sélectionnant INS pour visualiser pas à pas l'algorithme.

Essayez de remarquer les étapes récurrentes, et les deux fonctions codées précedemment. Cela vous aidera à construire la boucle nécessaire dans l'algorithme.

Solution 
def tri_insertion(l):
    """
    Trie la liste l par ordre croissant selon l'algorithme du tri par insertion.
    Entrées : l - list : Liste à trier
    Sorties : None
    """
    for i in range(len(l)):
        indice = position_tri(l, i, l[i])
        deplacer(l, indice, i)

ma_liste = [3, 7, 2, 8, 1]
tri_selection(ma_liste)
print(ma_liste)  # Doit afficher [1, 2, 3, 7, 8]