TP n°12 (tris) : Éléments de correction

I. Création de listes-tests et temps d'exécution¶

Exercice 1

In [1]:

import random as rd

In [2]:

def gen(n, N):
    return [rd.randint(0, N) for i in range(n)]

In [3]:

gen(6, 4)

Out[3]:

[4, 1, 0, 1, 1, 3]

Exercice 2

In [4]:

from time import process_time as toc

In [5]:

ping, pong, N = 0, 1, 10**8
t1 = toc()
for k in range(N):
    ping, pong = pong, ping
t2 = toc()
print(t2 - t1)

7.541157999999999

II. Tris en place¶

Exercice 3 : tri par sélection

On écrit d'abord une fonction qui détermine l'indice du minimum de la liste L à partir de l'indice i:

In [6]:

def minpos(L, i):
    j = i
    m = L[i]
    for k in range(i + 1, len(L)):
        if L[k] < m:
            j = k
            m = L[k]
    return j

Remarque : la recherche du minimum d'une liste et de l'indice correspondant est à connaître par cœur.

In [7]:

def select(L):
    n = len(L)
    for i in range(n - 1):
        j = minpos(L,i)
        L[i], L[j] = L[j], L[i]
    return None

Remarque : le principe d'utiliser une fonction à l'intérieur d'une autre est très classique en informatique, et souvent recommandé !

In [8]:

L = gen(10, 20)
print(L)
select(L)
print(L)

[6, 4, 13, 17, 17, 8, 1, 6, 10, 8]
[1, 4, 6, 6, 8, 8, 10, 13, 17, 17]

In [9]:

N = 10**3
Tselect = []
for p in range(1, 5):
    n = 10**p
    L = gen(n, N)
    t1 = toc()
    select(L)
    t2 = toc()
    Tselect.append(t2 - t1)
print(Tselect)

[1.4000000000180535e-05, 0.00025599999999936784, 0.026517999999999375, 2.4569980000000005]

Exercice 4 : tri par insertion

Là encore, on écrit une fonction auxiliaire :

In [10]:

def deplacer(L, k, i):
    """
    Déplace l'élément k de la liste L entre L[i] et L[i+1]
    """
    elt = L.pop(k)
    L.insert(i + 1, elt)
    return None

In [11]:

def insertion(L):
    n = len(L)
    for k in range(1, n):
        i = k - 1
        elt = L[k]
        while i >= 0 and elt < L[i]:
            i -= 1
        deplacer(L,k,i)
    return None

In [12]:

L = gen(10, 20)
print(L)
insertion(L)
print(L)

[20, 16, 15, 11, 19, 11, 5, 16, 5, 1]
[1, 5, 5, 11, 11, 15, 16, 16, 19, 20]

In [13]:

N = 10**3
Tinsert = []
for p in range(1, 5):
    n = 10**p
    L = gen(n, N)
    t1 = toc()
    insertion(L)
    t2 = toc()
    Tinsert.append(t2 - t1)
print(Tinsert)

[8.999999998593466e-06, 0.00018099999999954264, 0.020491999999999067, 1.943506000000001]

Exercice 5 : tri par insertion (sans insert)

Pour se passer la méthode insert, on effectue des affectations successives en même temps que la recherche de l'indice d'insertion :

In [14]:

def insertion(L):
    n = len(L)
    for k in range(1, n):
        i = k
        elt = L[k]
        while i > 0 and L[i - 1] > elt:
            L[i] = L[i - 1]
            i -= 1
        L[i] = elt
    return L

In [15]:

L = gen(10, 20)
print(L)
insertion(L)
print(L)

[15, 3, 20, 18, 17, 5, 19, 4, 3, 2]
[2, 3, 3, 4, 5, 15, 17, 18, 19, 20]

In [16]:

N = 10**3
Tinsertion = []
for p in range(1, 5):
    n = 10**p
    L = gen(n, N)
    t1 = toc()
    insertion(L)
    t2 = toc()
    Tinsertion.append(t2 - t1)
print(Tinsertion)

[8.000000001118224e-06, 0.00035600000000002296, 0.03854199999999963, 4.040872000000002]

C'est évidemment un peu moins efficace qu'avec l'utilisation de insert...

III. Tris récursifs¶

Exercice 6 : tri fusion

In [17]:

def fusion(A, B):
    if len(A) == 0:
        return B
    elif len(B) == 0:
        return A
    elif A[0] < B[0]:
        return [A[0]] + fusion(A[1:], B)
    else:
        return [B[0]] + fusion(A, B[1:])

In [18]:

def tri_fusion(L):
    n = len(L)
    if n <= 1:
        return L
    else:
        mil = n // 2
        return fusion(tri_fusion(L[:mil]), tri_fusion(L[mil:]))

In [19]:

L = gen(10, 20)
print(L)
print(tri_fusion(L))

[7, 14, 14, 16, 7, 11, 20, 10, 12, 2]
[2, 7, 7, 10, 11, 12, 14, 14, 16, 20]

In [20]:

N = 10**3
Tfusion = []
for p in range(1, 4):
    n = 10**p
    L = gen(n, N)
    t1 = toc()
    tri_fusion(L)
    t2 = toc()
    Tfusion.append(t2 - t1)
print(Tfusion)

[2.3000000002326715e-05, 0.00039199999999794954, 0.010486000000000217]

L'appel de tri_fusion avec une liste de taille supérieure provoque une erreur de récursivité : trop d'appels récursifs ont été effectués, et Python arrête l'éxécution de la fonction :

What Causes RecursionError

A RecursionError in Python is caused by a function calling itself recursively without a proper base case. Python has a limit on the number of times a function can call itself recursively. This is to ensure that the function does not execute indefinitely. If this limit is exceeded by a recursive function, a RecursionError is raised.

In [21]:

n = 10**4
N = 10**4
L = gen(n, N)
tri_fusion(L)

---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
<ipython-input-21-46e6e580fa6c> in <module>
      2 N = 10**4
      3 L = gen(n, N)
----> 4 tri_fusion(L)

<ipython-input-18-0077635933dc> in tri_fusion(L)
      5     else:
      6         mil = n // 2
----> 7         return fusion(tri_fusion(L[:mil]), tri_fusion(L[mil:]))

<ipython-input-18-0077635933dc> in tri_fusion(L)
      5     else:
      6         mil = n // 2
----> 7         return fusion(tri_fusion(L[:mil]), tri_fusion(L[mil:]))

<ipython-input-17-10eca19b6eb2> in fusion(A, B)
      7         return [A[0]] + fusion(A[1:], B)
      8     else:
----> 9         return [B[0]] + fusion(A, B[1:])

<ipython-input-17-10eca19b6eb2> in fusion(A, B)
      7         return [A[0]] + fusion(A[1:], B)
      8     else:
----> 9         return [B[0]] + fusion(A, B[1:])

<ipython-input-17-10eca19b6eb2> in fusion(A, B)
      7         return [A[0]] + fusion(A[1:], B)
      8     else:
----> 9         return [B[0]] + fusion(A, B[1:])

<ipython-input-17-10eca19b6eb2> in fusion(A, B)
      5         return A
      6     elif A[0] < B[0]:
----> 7         return [A[0]] + fusion(A[1:], B)
      8     else:
      9         return [B[0]] + fusion(A, B[1:])

<ipython-input-17-10eca19b6eb2> in fusion(A, B)
      5         return A
      6     elif A[0] < B[0]:
----> 7         return [A[0]] + fusion(A[1:], B)
      8     else:
      9         return [B[0]] + fusion(A, B[1:])

<ipython-input-17-10eca19b6eb2> in fusion(A, B)
      5         return A
      6     elif A[0] < B[0]:
----> 7         return [A[0]] + fusion(A[1:], B)
      8     else:
      9         return [B[0]] + fusion(A, B[1:])

<ipython-input-17-10eca19b6eb2> in fusion(A, B)
      7         return [A[0]] + fusion(A[1:], B)
      8     else:
----> 9         return [B[0]] + fusion(A, B[1:])

<ipython-input-17-10eca19b6eb2> in fusion(A, B)
      5         return A
      6     elif A[0] < B[0]:
----> 7         return [A[0]] + fusion(A[1:], B)
      8     else:
      9         return [B[0]] + fusion(A, B[1:])

<ipython-input-17-10eca19b6eb2> in fusion(A, B)
      5         return A
      6     elif A[0] < B[0]:
----> 7         return [A[0]] + fusion(A[1:], B)
      8     else:
      9         return [B[0]] + fusion(A, B[1:])

<ipython-input-17-10eca19b6eb2> in fusion(A, B)
      5         return A
      6     elif A[0] < B[0]:
----> 7         return [A[0]] + fusion(A[1:], B)
      8     else:
      9         return [B[0]] + fusion(A, B[1:])

<ipython-input-17-10eca19b6eb2> in fusion(A, B)
      5         return A
      6     elif A[0] < B[0]:
----> 7         return [A[0]] + fusion(A[1:], B)
      8     else:
      9         return [B[0]] + fusion(A, B[1:])

<ipython-input-17-10eca19b6eb2> in fusion(A, B)
      5         return A
      6     elif A[0] < B[0]:
----> 7         return [A[0]] + fusion(A[1:], B)
      8     else:
      9         return [B[0]] + fusion(A, B[1:])

... last 12 frames repeated, from the frame below ...

<ipython-input-17-10eca19b6eb2> in fusion(A, B)
      7         return [A[0]] + fusion(A[1:], B)
      8     else:
----> 9         return [B[0]] + fusion(A, B[1:])

RecursionError: maximum recursion depth exceeded while calling a Python object

Exercice 7 : tri rapide

In [22]:

def quicksort(L):
    n = len(L)
    if n <= 1:
        return L
    else:
        pivot = L[0]
        G = [l for l in L[1:] if l <= pivot]
        D = [l for l in L[1:] if l > pivot]
        return quicksort(G) + [pivot] + quicksort(D)

Les listes par compréhension, c'est bien, mais ici ça fait parcourir 2 fois la liste L[1:]. On peut l'éviter de la manière suivante :

In [23]:

def quicksort(L):
    n = len(L)
    if n < 2:
        return L
    else:
        pivot = L[0]
        G, D = [], []
        for elt in L[1:]:
            if elt > pivot:
                D.append(elt)
            else:
                G.append(elt)
        return quicksort(G) + [pivot] + quicksort(D)

In [24]:

L = gen(10, 20)
print(L)
print(quicksort(L))

[19, 17, 18, 7, 0, 7, 19, 9, 18, 8]
[0, 7, 7, 8, 9, 17, 18, 18, 19, 19]

In [25]:

N = 10**3
Trapide = []
for p in range(1, 5):
    n = 10**p
    L = gen(n, N)
    t1 = toc()
    quicksort(L)
    t2 = toc()
    Trapide.append(t2 - t1)
print(Trapide)

[6.800000000239947e-05, 0.0003740000000007626, 0.004339999999999122, 0.03511800000000065]

Remarque : c'est extrêmement rapide. Une amélioration classique consiste à prendre comme pivot un élément aléatoire de la liste L.

IV. Autres algorithmes de tri¶

Exercice 8 : tri par comptage

In [26]:

def comptage(L, N):
    """
    Les entiers de la liste L doivent être compris entre 0 et N
    """
    n = len(L)
    T = (N + 1) * [0]
    for elt in L:
        T[elt] += 1
    # reconstruction de la liste ordonnée :
    R= []
    for elt in range(N+1):
        for j in range(T[elt]):
            R.append(elt)
    return R

On peut écrire la reconstruction de la liste ordonnée en utilisant des listes par compréhension :

In [27]:

def comptage(L, N):
    """
    Les entiers de la liste L doivent être compris entre 0 et N
    """
    n = len(L)
    T = (N + 1) * [0]
    for elt in L:
        T[elt] += 1
    # le retour des listes par compréhension !!
    L = [[elt] * T[elt] for elt in range(N + 1) if T[elt] > 0]
    return [j for elt in L for j in elt]

In [28]:

L = gen(10, 20)
print(L)
print(comptage(L,20))

[4, 1, 3, 19, 9, 16, 2, 8, 1, 9]
[1, 1, 2, 3, 4, 8, 9, 9, 16, 19]

In [29]:

N = 10**3
Tcomptage = []
for p in range(1, 4):
    n = 10**p
    L = gen(n, N)
    t1 = toc()
    for k in range(N):
        comptage(L,N)
    t2 = toc()
    Tcomptage.append(t2 - t1)
print(Tcomptage)

[0.0944970000000005, 0.0676819999999978, 0.21398500000000098]

Exercice 9 : tri bulle

In [30]:

def bulle(L):
    for i in range(len(L) - 1, 0, -1):
        for j in range(i):
            if L[j+1] < L[j]:
                L[j], L[j + 1] = L[j + 1], L[j]
    return None

In [31]:

L = gen(10, 20)
print(L)
bulle(L)
print(L)

[2, 9, 4, 19, 12, 13, 9, 15, 1, 6]
[1, 2, 4, 6, 9, 9, 12, 13, 15, 19]

In [32]:

N = 10**3
Tbulle = []
for p in range(1, 5):
    n = 10**p
    L = gen(n, N)
    t1 = toc()
    bulle(L)
    t2 = toc()
    Tbulle.append(t2 - t1)
print(Tbulle)

[2.9000000001389026e-05, 0.0016200000000026193, 0.10975800000000291, 7.336446000000002]

Exercice 10 : tri par paquets

In [33]:

def paquets(L):
    """
    L est une liste de flottants compris entre 0 et 1
    """
    n = len(L)
    P = [[] for k in range(n)]  # les paquets
    for elt in L:
        k = int(n * elt)  # la partie entière
        P[k].append(elt)
    for k in range(n):
        insertion(P[k])  # on trie le paquet
    return [j for elt in P for j in elt]

In [34]:

n = 10
L = [rd.random() for i in range(n)]
print(paquets(L))

[0.02062139653381445, 0.24595653164188402, 0.24715362970524113, 0.2650980712060912, 0.2877848491058531, 0.3182107344428493, 0.3940554980850074, 0.3971520879069267, 0.6277108094001935, 0.8171620325517714]

Dans le cas où la liste $L$ est constituée de flottants compris de $[a,b[$, on peut procéder ainsi :

Créer $n$ listes $P_0, \ldots, P_{n-1}$ appelées paquets. Le paquet $P_k$ est associé à l'intervalle $I_k=\left[a+k(b-a) / n, a+(k+1)(b-a) / n\right[$.
Pour chaque élément $L[i]$ :
- Calculer l'intervalle $I_k$ dans lequel il se trouve : $k=\left\lfloor n(L[i]-a) /(b-a)\right\rfloor$
- Ajouter $L[i]$ à $P_k$.
Trier chaque liste $P_k$, par exemple avec un tri par insertion.
Renvoyer la concaténation des listes $P_0, \ldots, P_{n-1}$.