On peut appliquer le principe de la dichotomie, "couper en deux", sur des problèmes où c'est moins évident : soit on arrive à ne traiter qu'une seule des deux parties (exponentiation rapide), soit on traite les deux parties indépendamment, avant de combiner les résultats (tri fusion, tri rapide).

I. Exponentiation rapide

Ici, en prenant un flottant (c'est-à-dire un nombre à virgule) et un entier positif, on veut calculer de manière efficace.

Méthode naïve : on peut faire pour un total de multiplications.

Mais on peut faire mieux ! Par exemple :

• Considérons . On a . Si on nomme , il nous faut une multiplication pour calculer , puis une multiplication pour calculer . On a économisé une multiplication !
• Et si est impair ? Par exemple . Dans ce cas, on découpe comme suit : , et on calcule comme précédemment.

def exp_rapide(x, n):
    """Calcule x^n en O(log(n)), avec x un flottant et n un entier positif"""
    reste = 1
    while n != 0:
        if n % 2 == 0:
            n //= 2
            x *= x
        else:
            reste *= x
            n -= 1
    return reste

print(exp_rapide(5, 7), 5 ** 7)
print(exp_rapide(2, 100))
print(exp_rapide(1.5, 10))

Voici les valeurs successives des variables lors du calcul de :

On peut obtenir ce tableau automatiquement avec tracer_variables :

II. Tri fusion

On va réutiliser l'idée de couper en deux, mais cette fois pour trier une liste. Le tri fusion (ou "partition-fusion") est en 3 étapes :

1. Couper la liste à trier en deux parts égales.
2. Trier chaque partie séparément.
3. Fusionner les deux parties triées.

On va s'intéresser à ces étapes une par une.

a) Couper la liste en deux

def partition(L):
    """Prend une liste en argument, et renvoie deux nouvelles listes contenant chacune la moitié des éléments (avec un de plus dans la deuxième si nécessaire)"""
    n = len(L)
    milieu = n//2

    moitie_1 = L[0:milieu]
    moitie_2 = L[milieu:n]

    return (moitie_1, moitie_2)

partition([4, 1, 2, 8, 3, 1, 9])

b) Trier chaque partie séparément

On va trier les parties en utilisant... le tri fusion lui-même !

c) Fusionner deux listes triées

Idée : on aimerait placer tous les éléments contenus dans les deux listes moitie_1 et moitie_2 dans une nouvelle liste resultat. On va prendre les éléments un par un !

def fusion(L1, L2):
    """fusionne deux listes triées en ordre croissant en une seule liste triée également."""
    resultat = []
    i1 = 0
    i2 = 0
    #On transfère les éléments tant qu'on n'a terminé aucune des deux listes
    while i1 < len(L1) and i2 < len(L2):
        if L1[i1] < L2[i2]:
            resultat.append(L1[i1])
            i1 += 1
        else:
            resultat.append(L2[i2])
            i2 += 1

    #Une fois qu'une liste est terminée, on peut transférer tout ce qu'il reste dans l'autre !
    reste1 = L1[i1:]
    reste2 = L2[i2:]

    resultat = resultat + reste1 + reste2

    #Un seul des deux restes sera non vide (grâce à la condition du "while")

    return resultat

fusion([1, 4, 8, 9], [1, 2, 3, 10])

Pour visualiser la fusion, voici la même fonction, qui note chaque étape pour l'animer avec animer_liste. On affiche L1, puis L2, puis le résultat en cours de construction ; les deux éléments comparés sont en rouge :

d) En combinant les trois

def tri_fusion(L):
    if len(L) <= 1:
        return L[:]
    #partition
    moitie_1, moitie_2 = partition(L)

    #tri récursif
    moitie_1 = tri_fusion(moitie_1)
    moitie_2 = tri_fusion(moitie_2)

    #fusion
    return fusion(moitie_1, moitie_2)

III. Tri rapide

Le tri rapide découpe lui aussi la liste en deux, mais différemment : on choisit un élément, le pivot (par exemple le premier), et on sépare les autres éléments en deux listes, ceux qui sont plus petits que le pivot et ceux qui sont plus grands. Il reste à trier ces deux listes (récursivement), et à les mettre bout à bout, avec le pivot au milieu. Il n'y a plus besoin de fusion !

def tri_rapide(L):
    if len(L) <= 1:
        return L[:]
    pivot = L[0]
    plus_petits = []
    plus_grands = []
    for x in L[1:]:
        if x < pivot:
            plus_petits.append(x)
        else:
            plus_grands.append(x)
    return tri_rapide(plus_petits) + [pivot] + tri_rapide(plus_grands)

print(tri_rapide([4, 1, 2, 8, 3, 1, 9]))

from affichage import animer_tri
animer_tri(tri_rapide, [5, 9, 2, 7, 1, 8, 3, 6, 4, 10, 12, 11])

En pratique, le tri rapide est souvent très rapide (d'où son nom), surtout si on choisit le pivot au hasard et pas comme le premier élément.

Exercices

def fusion_rec(L1, L2):
    if len(L1) == 0:
        return L2[:]
    if len(L2) == 0:
        return L1[:]
    if L1[0] <= L2[0]:
        return [L1[0]] + fusion_rec(L1[1:], L2)
    return [L2[0]] + fusion_rec(L1, L2[1:])

from random import randint

def tri_rapide_hasard(L):
    if len(L) <= 1:
        return L[:]
    k = randint(0, len(L) - 1)
    pivot = L[k]
    autres = L[:k] + L[k+1:]
    plus_petits = [x for x in autres if x < pivot]
    plus_grands = [x for x in autres if x >= pivot]
    return tri_rapide_hasard(plus_petits) + [pivot] + tri_rapide_hasard(plus_grands)

def exp_rapide_rec(x, n):
    if n == 0:
        return 1
    y = exp_rapide_rec(x, n // 2)
    if n % 2 == 0:
        return y * y
    return x * y * y

def tri_fusion_inversions(L):
    """Renvoie la liste triée et le nombre d'inversions."""
    if len(L) <= 1:
        return L[:], 0
    milieu = len(L) // 2
    L1, n1 = tri_fusion_inversions(L[:milieu])
    L2, n2 = tri_fusion_inversions(L[milieu:])
    resultat, inversions = [], n1 + n2
    i1 = i2 = 0
    while i1 < len(L1) or i2 < len(L2):
        if i1 < len(L1) and (i2 == len(L2) or L1[i1] <= L2[i2]):
            resultat.append(L1[i1])
            i1 += 1
        else:
            resultat.append(L2[i2])
            inversions += len(L1) - i1
            i2 += 1
    return resultat, inversions

tri_fusion_inversions([3, 1, 2, 5, 4])   # 3 inversions : (3, 1), (3, 2), (5, 4)