Diviser pour régner

9. Diviser pour régner#

9.1. Tri Fusion#

On a vu en Première le tri par insertion et le tri à bulles. Ces algorithmes de tri ont été l’occasion de s’initier à un questionnement sur les algorihtmes :

  1. l’algorihtme termine-t-il ? Dans certains cas ou dans tous les cas ?

  2. l’algorihtme est-il est correct ? (fait-il ce qu’il doit faire ?)

  3. l’algorihtme est-il efficace ? (quel est, en fonction de la taille de l’entrée, l’ordre de grandeur du nombre d’opérations)

On peut rappeller certains notations :

  • \(O(1)\) signifie que la taille de l’entrée n’a pas d’incidence sur le nombre d’opérations. On parle de complexité constante.

  • \(O(n)\) signifie que, lorsque l’entrée double, le nombre d’opération double lui aussi. On parle de complexité linéaire.

  • \(O(n^2\)) signifie que, lorsque l’entrée double, le nombre d’opération est multiplié par 4. On parle de complexité quadratique.

9.2. Principe général#

Le principe du tri fusion est diviser la liste en deux listes de taille identique, de les trier et de fusionner les listes ainsi triée pour obtenir une liste triée. Pour trier les deux sous-listes, on peut répéter l’algorithme et on a donc un algorithme récursif. La condition d’arrêt «naturelle» est qu’une liste à 1 élément est nécessairement triée.

Cette méthode fait partie des méthodes de type diviser pour régner.

Algorithm 9.1

Entrée : Liste Sortie : Liste Procédure : Diviser la liste en deux Procédure : Fusionner deux listes triées en une liste triée Procédure : Trier Traitement (Trier) : Partager Liste -> deux listes A et B Fusionner(Trier(A), Trier(B))

def partage(L):
    """prend une liste L et renvoie un couple de deux listes de taille identique (à l'unité près) de sorte que leur réunion soit la liste L de départ """
    n = len(L)
    if n < 2:
        return L, []
    else:
        p = n // 2
        q = n - p
        L1, L2 = [0] * q, [0] * p
        for i in range(n):
            if i < q:
                L1[i] = L[i]
            else:
                L2[i - q] = L[i]
        return L1, L2

def fusion(L1, L2):
    '''réalise la fusion de deux listes triées, le résultat est une liste triée'''
    n1, n2 = len(L1), len(L2)
    n = n1 + n2
    L = [0] * n
    i, i1, i2 = 0, 0, 0
    while i1 < n1 and i2 < n2:
        if L1[i1] < L2[i2]:
            L[i] = L1[i1]
            i1 = i1 + 1
        else:
            L[i] = L2[i2]
            i2 = i2 + 1
        i += 1
    # ici on a vidé l'une ou l'autre des deux listes
    # s'il faut encore vider L1
    while i1 < n1:
        L[i] = L1[i1]
        i1 += 1
        i += 1
    # s'il faut encore vider L2
    while i2 < n2:
        L[i] = L2[i2]
        i2 += 1
        i += 1
    return L

def tri(L):
    if len(L) < 2:
        return L
    else:
        L1, L2 = partage(L)
        return fusion(tri(L1), tri(L2))

from random import randint

%%timeit L = [randint(0,15) for _ in range(15)]
tri(L)

18.1 μs ± 352 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

%%timeit L = [randint(0,15) for _ in range(15)]
sorted(L)

429 ns ± 19.8 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
Contenu