TP 9 : Algorithmes de tri

On souhaite trier une liste L, c'est-à-dire réarranger ses éléments pour qu'ils soient rangés dans l'ordre croissant.
Par exemple, si L = [5, 1, -4, 2, -8, 7] alors un algorithme de tri doit permettre d'obtenir la liste [-8, -4, 1, 2, 5, 7].
Dans ce TP, nous étudions plusieurs algorithmes de tri. Pensez à bien tester toutes vos fonctions.

Tri par sélection¶

Le tri par sélection consiste à chercher le minimum que l'on met en 1ère position de la liste, puis le 2ème plus petit élément en 2ème position...

Exercice

Écrire une fonction minimum(L, i) qui renvoie l'indice du minimum de la liste L à partir de la position i.
Par exemple, si L = [5, 1, -8, 2, -4, 7], minimum(L, 0) doit renvoyer 2 (correspondant à L[2] = -8) et minimum([5, 1, -8, 2, -4, 7], 3) doit renvoyer 4 (correspondant à L[4] = -4).

Solution

In [1]:

def minimum(L, i):
    m = i
    for j in range(i, len(L)):
        if L[j] < L[m]:
            m = j
    return m

L = [5, 1, -8, 2, -4, 7]
minimum(L, 0) == 2 and minimum(L, 3) == 4

def minimum(L, i): m = i for j in range(i, len(L)): if L[j] < L[m]: m = j return m L = [5, 1, -8, 2, -4, 7] minimum(L, 0) == 2 and minimum(L, 3) == 4

Out[1]:

True

Exercice

Écrire une fonction tri_selection(L) qui trie une liste L en utilisant le tri par sélection. On pourra compléter le code suivant :

def tri_selection(L):
    for i in range(len(L)):
        m = minimum(L, i)
        # échanger L[i] et L[m]

Solution

In [2]:

def tri_selection(L):
    for i in range(len(L)):
        m = minimum(L, i)
        L[i], L[m] = L[m], L[i] # échanger L[i] et L[m]
    return L

L = [5, 1, -8, 2, -4, 7]
tri_selection(L)
L

def tri_selection(L): for i in range(len(L)): m = minimum(L, i) L[i], L[m] = L[m], L[i] # échanger L[i] et L[m] return L L = [5, 1, -8, 2, -4, 7] tri_selection(L) L

Out[2]:

[-8, -4, 1, 2, 5, 7]

Tri par insertion¶

Le tri par insertion consiste à trier progressivement la liste L, de gauche à droite. Plus précisément, à l'étape $i$, les $i$ premiers de L sont triés et on fait en sorte d'insérer le $i+1$ème élément L[i] au bon endroit pour que les $i + 1$ premiers éléments soient triés.
Voici les étapes du tri par insertion pour la liste L = [5, 1, -4, 2, -8, 7] :

• i = 0 : on insère L[0] = 5 de façon à ce que le 1er élément de L soit trié (il n'y a rien à faire : un élément seul est toujours trié). L vaut [5, 1, -4, 2, -8, 7] (on met en gras la partie de L déjà triée).
• i = 1 : on insère L[1] = 1 au bon endroit, ce qui donne [1, 5, -4, 2, -8, 7]
• i = 2 : on insère L[2] = -4 au bon endroit, ce qui donne [-4, 1, 5, 2, -8, 7]
• i = 3 : on insère L[3] = 2 au bon endroit, ce qui donne [-4, 1, 2, 5, -8, 7]
• i = 4 : on insère L[4] = -8 au bon endroit, ce qui donne [-8, -4, 1, 2, 5, 7]
• i = 5 : on insère L[5] = 7 au bon endroit, ce qui donne [-8, -4, 1, 2, 5, 7]

On a terminé, et la liste est bien triée.

Exercice

Ecrire une fonction position telle que, si L est une liste, i un indice de L et e une valeur, position(L, i, e) renvoie le plus petit indice j < i tel que L[j] > e. S'il n'existe pas de tel indice j, on renverra i.
Exemple : position([1, 5, -4, 2, -8, 7], 2, -4) doit renvoyer 0, position([-8, -4, 1, 2, 5, 7], 5, 7) doit renvoyer 5.
On pourra compléter le code suivant :

def position(L, i, e):
    for j in range(i):
        if ...:
            return ...
    return i

print(position([1, 5, -4, 2, -8, 7], 2, -4)) # test
print(position([-8, -4, 1, 2, 5, 7], 5, 7)) # test

Solution

In [14]:

def position(L, i, e):
    for j in range(i):
        if L[j] > e:
            return j
    return i

print(position([1, 5, -4, 2, -8, 7], 2, -4))
print(position([-8, -4, 1, 2, 5, 7], 5, 7))

def position(L, i, e): for j in range(i): if L[j] > e: return j return i print(position([1, 5, -4, 2, -8, 7], 2, -4)) print(position([-8, -4, 1, 2, 5, 7], 5, 7))

0
5

Exercice

Écrire une fonction decaler telle que decaler(L, i, j) décale les éléments de la liste L d'une position vers la droite. Ainsi, la valeur de L[i] doit être mise dans L[i + 1], L[i + 1] dans L[i + 2], ..., L[j - 1] doit être mise dans L[j].
Par exemple, après les instructions L = [1, 3, 6, 9, 17] et decaler(L, 1, 3), L doit contenir [1, 3, 3, 6, 17] (L[i] n'est pas modifié).

Solution

In [23]:

def decaler(L, i, j):
    for k in range(j, i, -1):
        L[k] = L[k - 1]

L = [1, 3, 6, 9, 17]
decaler(L, 1, 3)
L

def decaler(L, i, j): for k in range(j, i, -1): L[k] = L[k - 1] L = [1, 3, 6, 9, 17] decaler(L, 1, 3) L

Out[23]:

[1, 3, 3, 6, 17]

Exercice

En utilisant position et decaler, écrire une fonction tri_insertion qui trie une liste en utilisant le tri par insertion. On pourra compléter le code suivant :

def tri_insertion(L):
    for i in range(len(L)):
        p = ...
        decaler(...)
        ... # mettre l'anciennce valeur de L[i] dans L[p]

Solution

In [29]:

def tri_insertion(L):
    for i in range(len(L)):
        p = position(L, i, L[i])
        Li = L[i]
        decaler(L, p, i)
        L[p] = Li

L = [5, 1, -8, 2, -4, 7]
tri_insertion(L)
L

def tri_insertion(L): for i in range(len(L)): p = position(L, i, L[i]) Li = L[i] decaler(L, p, i) L[p] = Li L = [5, 1, -8, 2, -4, 7] tri_insertion(L) L

Out[29]:

[-8, -4, 1, 2, 5, 7]

Tri fusion (récursif)¶

Le tri fusion sur une liste L consiste à :

• Séparer L en deux listes L1 et L2 de même taille.
• Trier récursivement L1 et L2 pour obtenir des listes triées L1' et L2'.
• Fusionner L1' et L2' pour avoir un tri de L.
  Le tri fusion est donc récursif.

Illustration du tri fusion sur L = [5, 1, -4, 2, -8, 7] :

Dans l'exemple ci-dessus, on n'a pas détaillé l'exécution des appels récursifs.
Voici un exemple complètement détaillé du tri fusion sur L = [39, 27, 43, 3, 9, 82, 10], où les divisions sont représentées par des flèches rouges et les fusions avec des flèches vertes :

Exercice

Écrire une fonction division telle que division(L) renvoie deux listes L1 et L2 qui séparent L en deux listes de même taille (à $\pm 1$).

Solution

In [30]:

def division(L):
    L1, L2 = [], []
    for i in range(len(L)):
        if i < len(L)//2:
            L1.append(L[i])
        else:
            L2.append(L[i])
    return L1, L2

def division(L): L1, L2 = [], [] for i in range(len(L)): if i < len(L)//2: L1.append(L[i]) else: L2.append(L[i]) return L1, L2

Exercice

Écrire une fonction fusion telle que fusion(L1, L2) renvoie une liste L triée qui est la fusion de deux listes triées L1 et L2.
On pourra créer une nouvelle liste L, utiliser 2 indices i et j permettant de parcourir L1 et L2 (avec un while), et ajouter à L le minimum de L1[i] et L2[j].
Par exemple, fusion([1, 3, 6], [0, 4, 5] doit renvoyer [0, 1, 3, 4, 5, 6].

Solution

In [ ]:

def fusion(L1, L2):
    L = []
    i, j = 0, 0
    while i < len(L1) and j < len(L2):
        if L1[i] < L2[j]:
            L.append(L1[i])
            i += 1
        else:
            L.append(L2[j])
            j += 1
    L += L1[i:]
    L += L2[j:]
    return L

def fusion(L1, L2): L = [] i, j = 0, 0 while i < len(L1) and j < len(L2): if L1[i] < L2[j]: L.append(L1[i]) i += 1 else: L.append(L2[j]) j += 1 L += L1[i:] L += L2[j:] return L

Exercice

Écrire une fonction tri_fusion qui trie une liste en utilisant le tri fusion.