Tris récursifs

Version récursive du tri insertion

On écrit tout d'abord une version récursive de la fonction insertion(T, k).

def insertion(T, k):
    """ Insère l'élément T[k] à la bonne place
        dans la liste T[:k+1]. 
        La liste T[:k] est supposée être déjà triée.
    """

L'idée récursive est la suivante :

Pour insérer T[k] à la bonne place dans T[:k+1] :
    Si k = 0 ou si T[k - 1] < T[k] alors
        il n'y a rien à faire
    sinon
        on permute T[k - 1] et T[k]
        puis on insère T[k - 1] à la bonne place dans T[:k]
    finSi
In [ ]:
def insertion(T, k):
    """ Insère l'élément T[k] à la bonne place dans la liste T[:k+1]. 
        La liste T[:k] est supposée être déjà triée.
    """
    if k > 0 and T[k - 1] > T[k]:
        T[k - 1], T[k] = T[k], T[k - 1]
        insertion(T, k - 1)
[1, 3, 5, 8, 8, 9, 4, 2]
[0, 1, 5, 8, 8, 9, 4, 2]

Il s'agit maintenant d'écrire la fonction tri_insertion. Pour résoudre récursivement le problème du tri on introduit un paramètre $n$ qui sera la taille du problème :

def tri_insertion(T, n):
    """ Trie en place la liste T[:n] en utilisant l'algorithme
        du tri par insertion.
    """

L'idée récursive est alors la suivante :

Pour trier le tableau T[:n] :
    Si n = 0 ou 1 alors
        il n'y a rien à faire
    sinon
        on trie le tableau T[:n-1]
        puis on insére T[n-1] à la bonne place dans T
    finSi
In [ ]:
def tri_insertion(T, n):
    """ Trie en place la liste T[:n] en utilisant l'algorithme
        du tri par insertion.
    """
    if n > 1:
        tri_insertion(T, n - 1)
        insertion(T, n - 1)
        
T = [4, 6, 2, 4, 0, 1]
tri_insertion(T, len(T))
print(T)      
[0, 1, 2, 4, 4, 6]

Complexité de la fonction tri_insertion

Étudions tout d'abord la complexité de insertion(T, k).

Soit $I(k)$ le temps d'exécution au pire de insertion(T, k). Il existe une constante $a$ telle que :

$$ \begin{cases} I(0) &\leq a \\ I(k) &\leq a + I(k-1) \end{cases} $$

$I(k) \leq a + I(k-1) \leq 2a + I(k-2) \leq ka + I(0) \leq (k + 1)a$

Dans le pire des cas insertion(T, k) s'exécute en $O(k)$.

Appelons $C(n)$ le temps d'exécution au pire de tri_insertion(T, n). Il existe une constante $a$ telle que :

$$ \begin{cases} C(1) &\leq a \\ C(n) &\leq na + C(n-1) \end{cases} $$

$C(n) \leq na + C(n-1) \leq na + (n-1)a + C(n-2) \leq \sum_{i=1}^n ia \leq \frac{n(n+1)a}{2}$

Dans le pire des cas tri_insertion(T, n) s'exécute en $O(n^2)$.

Amélioration du code

Il n'est pas très agréable de devoir passer la longueur de T en deuxième argument de tri_insertion. On peut éviter cela en écrivant le code de cette façon :

In [ ]:
def tri_insertion(T, n=None):
    """ Trie en place la liste T[:n] en utilisant l'algorithme
        du tri par insertion.
    """
    if n == None:
        n = len(T)
    if n > 1:
        tri_insertion(T, n - 1)
        insertion(T, n - 1)

T = [4, 6, 2, 4, 0, 1]
tri_insertion(T)
print(T)      
[0, 1, 2, 4, 4, 6]

La fonction insertion(T, k) est une fonction auxilliaire qui n'est utile que pour la fonction tri_insertion. Dans cette situation il est possible et souhaitable de définir la fonction insertion localement à l'intérieur de la fonction tri_insertion. C'est un bon principe que de limiter la visibilité d'un objet au code qui en a réellement besoin.

In [ ]:
def tri_insertion(T, n=None):
    """ Trie en place la liste T[:n] en utilisant l'algorithme
        du tri par insertion.
    """
    def insertion(T, k):
        if k > 0 and T[k - 1] > T[k]:
            T[k - 1], T[k] = T[k], T[k - 1]
            insertion(T, k - 1)  
            
    if n == None:
        n = len(T)
    if n > 1:
        tri_insertion(T, n - 1)
        insertion(T, n - 1)
        
T = [4, 6, 2, 4, 0, 1]
tri_insertion(T)
print(T)      
[0, 1, 2, 4, 4, 6]

Tri fusion

La méthode de tri par insertion peut être décrite aussi bien de façon itérative que de façon récursive. Nous allons maintenant exploiter une autre idée pour trier un tableau. Cette idée, pleinement récursive, est la suivante :

Pour trier une liste, il suffit de trier les moitiés gauche et droite séparément puis de fusionner ces deux moitiés.

Pour trier le tableau T
    Si longueur(T) <= 1 alors
        il n'y a rien à faire
    sinon
        Soit m la partie entière de la moitié de longueur(T)
        Trier T[:m]
        Trier T[m:]
        Fusionner T[:m] et T[m:]
    finsi

La fusion des deux moitiés est difficilement réalisable en place, c'est-à-dire par des permutations des éléments du tableau. Il est beaucoup plus simple de créer un nouveau tableau qui contiendra les deux moitiés fusionnées. Du coup, la fonction tri_fusion que nous allons écrire ne modifiera pas le tableau passé en argument mais retournera un nouveau tableau correctement trié.

Fonction tri_fusion(T)
    Si longueur(T) <= 1 alors
        Retourner une copie de T
    sinon
        Soit m la partie entière de la moitié de longueur(T)
        G <- tri_fusion(T[:m])
        D <- tri_fusion(T[m:])
        Retourner fusion(G, D)
    finsi
In [ ]:
def tri_fusion(T):
    """ Retourne une copie triée de T.
    """   
    if len(T) <= 1:
        return T.copy()
    else:
        m = len(T) // 2
        G = tri_fusion(T[:m])
        D = tri_fusion(T[m:])
        return fusion(G, D)

Il nous reste à écrire la fonction fusion(G, D).

L'algorithme consiste à créer un tableau R de longueur la somme des longueurs de G et de D et à remplir ce tableau à l'aide d'une boucle. On utilise trois variables de boucle u, v et k et on maintient vraie la propriété :

k == u + v et R[:k] contient les éléments de G[:u] et D[:v] correctement triés.

À chaque itération il s'agit de savoir lequel de G[u] ou de D[v] doit être copié en R[k].

In [ ]:
def fusion(G, D):
    """ Retourne la liste triée obtenue en fusionnant les 
        deux listes triées G et D.
    """
    n = len(G) + len(D)
    R = [0] * n
    u = 0
    v = 0
    for k in range(n):
        if u < len(G) and (v == len(D) or G[u] <= D[v]):
            R[k] = G[u]
            u = u + 1
        else:
            R[k] = D[v]
            v = v + 1
    return R

On peut simplifier le test en ajoutant au départ $+\infty$ à la fin des deux listes G et D.

In [ ]:
def fusion(G, D):
    """ Retourne la liste triée obtenue en fusionnant les 
        deux listes triées G et D.
    """
    n = len(G) + len(D)
    infini = 1e309  # 1e309 est égal au flottant +infini.
    G.append(infini)
    D.append(infini)
    R = [0] * n
    u = 0
    v = 0
    for k in range(n):
        if G[u] <= D[v]:
            R[k] = G[u]
            u = u + 1
        else:
            R[k] = D[v]
            v = v + 1
    return R

Complexité de tri_fusion

La fonction fusion(G, D) s'exécute en $O(n)$ où $n$ est la somme des longueurs de G et D.

Pour analyser la complexité de fusion(T) nous allons supposer que la longueur de T est une puissance de deux. Ceci permet d'éviter des complications techniques.

Soit $n=2^p$ la longueur de T et soit $C(n)$ le coût de tri_fusion(T).

Lorsque $n\gt 1$ l'appel tri_fusion(T[:m]) crée la copie T[:m] et exécute la fonction tri_fusion sur cette copie. Le coût de cet appel est donc $O(n)+C\left(\frac{n}{2}\right)$. On a ainsi $C(n) = 2\left(O(n)+C\left(\frac{n}{2}\right)\right)+O(n)=O(n)+2C\left(\frac{n}{2}\right)$.

Par conséquent :

$$ \begin{cases} C(1) &\leq a \\ C(n) &\leq na + C\left(\frac{n}{2}\right) \end{cases} $$

On en déduit que

\begin{align} C(n) &\leq na + 2C\left(\frac{n}{2}\right) \\ C\left(2^p\right) &\leq 2^pa + 2C\left(2^{p-1}\right) \\ C\left(2^p\right) &\leq 2^pa + 2\left[2^{p-1}a + 2C\left(2^{p-2}\right)\right] \\ C\left(2^p\right) &\leq 2\times 2^pa + 2^2C\left(2^{p-2}\right) \\ C\left(2^p\right) &\leq 3\times 2^pa + 2^3C\left(2^{p-3}\right) \\ C\left(2^p\right) &\leq p\times 2^pa + 2^pC\left(1\right) \\ C(n) &\leq n\log_2n + nC(1) \\ C(n) &= O(n\log n) \end{align}

La complexité de la fonction tri_fusion est en $O(n\log n)$. Ceci est bien meilleur que le $O(n^2)$ du tri par insertion. La supériorité du tri fusion sur le tri insertion est d'autant plus grande que $n$ est grand.

Amélioration de la fonction tri_fusion

Comme nous l'avons dit plus haut, l'instruction tri_fusion(T[:m]) a pour premier effet de créer la copie T[:m]. Cette copie est inutile puisque tri_fusion ne modifie pas la liste passée en argument. Une façon d'éviter cette copie est d'écrire une fonction tri_fusion(T, i, j) qui trie la liste T uniquement entre les indices i et j - 1. On améliore ainsi l'efficacité de la fonction de tri. On ne change toutefois pas la complexité asymptotique en $O(n\log n)$.

Voici la version améliorée, où l'on a aussi défini localement la fonction fusion :

In [ ]:
def tri_fusion(T, i=0, j=None):
    """ Retourne une copie triée de la liste T[i:j].  
    """    
    
    def fusion(G, D):
        """ Retourne la liste triée obtenue en fusionnant les 
            deux listes triées G et D.
        """
        n = len(G) + len(D)
        infini = 1e309  # 1e309 est égal au flottant +infini.
        G.append(infini)
        D.append(infini)
        R = [0] * n
        u = 0
        v = 0
        for k in range(n):
            if G[u] <= D[v]:
                R[k] = G[u]
                u = u + 1
            else:
                R[k] = D[v]
                v = v + 1
        return R

    if j == None:
        j = len(T)
    if j - i <= 1:
        return T[i:j]
    else:
        G = tri_fusion(T, i, (i + j) // 2)
        D = tri_fusion(T, (i + j) // 2, j)
        return fusion(G, D) 
Out[ ]:
[0, 1, 2, 4, 4, 6]

Tri rapide

Voici une nouvelle idée pour trier une collection d'objets : on choisit un objet quelconque que l'on appelle le pivot. On sépare ensuite les objets en deux parties : ceux qui sont plus petits que le pivot et ceux qui sont plus grands que lui. Il ne reste plus alors qu'à trier chacune de ces deux parties en appliquant le même principe. Cette idée récursive est appelée le tri rapide.

Nous allons appliquer cette idée pour écrire une nouvelle fonction : tri_rapide(T). La question du choix du pivot se pose. On peut le choisir de façon aléatoire, ce qui présente un avantage comme nous le verrons plus loin. Toutefois, dans un premier temps, nous allons prendre le dernier élément du tableau comme pivot. Une autre question se pose : la fonction va-t-elle trier le tableau en place ou bien va-t-elle retourner une copie triée ? Le tri en place est a priori plus efficace car cela réduit les copies au strict nécessaire. Contrairement au tri fusion nous allons voir que le tri rapide se prête bien au tri en place.

Nous devons donc écrire une fonction partition(T) qui permute les éléments de T de telle sorte que le dernier élément T[n - 1] == x se retrouve à un indice k tel que :

$$\forall i\lt k,\ T[i]\leq x\quad\text{et}\quad \forall i\gt k,\ T[i]\gt x$$

partition(T) : Le problème

On code la fonction partition avec un algorithme itératif. On utilise deux variables de boucle u et v en maintenant vraie la propriété :

$$ i\lt u \Longrightarrow T[i]\lt x\quad\text{et}\quad u\leq i\lt v \Longrightarrow T[i]\geq x$$

partition(T) : L'algorithme

In [ ]:
def partition(T):
    """ Soit x = T[n - 1].
        Modifie T de telle sorte que les éléments
        inférieurs strictement à x soient au début.
        Retourne le plus petit indice k telle T[k] >= x
    """
    n = len(T)
    x = T[n - 1]
    u = 0
    v = 0
    while v < n - 1:
        # Invariant de boucle :
        # i < u => T[i] < x
        # u <= i < v => T[i] >= x
        if T[v] < x:
            T[u], T[v] = T[v], T[u]
            u = u + 1
        v = v + 1
    T[u], T[n - 1] = T[n - 1], T[u]
    return u

T = [3, 6, 3, 1, 9, 2, 0, 4, 3]
partition(T)
print(T)
[1, 2, 0, 3, 9, 6, 3, 4, 3]

L'algorithme du tri rapide se réduit alors simplement à :

Fonction tri_rapide(T)
    Si longueur(T) <= 1 alors
        il n'y a rien à faire
    sinon
        k <- partition(T)
        tri_rapide(T[:k])
        tri_rapide(T[k+1:])
    finSi

Cet algorithme ne peut cependant pas se traduire tel quel en Python. En effet, l'évaluation de T[:k] crée une copie et c'est cette copie qui est passée à la fonction tri_rapide. Il faut plutôt passer à tri_rapide le tableau T original en lui indiquant de plus les indices entre lesquels la fonction doit travailler. La spécification de la fonction tri_rapide doit donc plutôt être la suivante :

def tri_rapide(T, i, j):
    """ Trie en place la sous-liste T[i:j].  
    """

Cette fonction est facile à écrire :

In [ ]:
def tri_rapide(T, i, j):
    """ Trie en place la sous-liste T[i:j].  
    """
    if j - i > 1:
        k = partition(T, i, j)
        tri_rapide(T, i, k)
        tri_rapide(T, k + 1, j)

On voit cependant qu'il est également nécessaire de modifier la spécification de la fonction partition :

In [ ]:
def partition(T, i, j):
    """ Soit x = T[j - 1].
        Modifie T[i:j] de telle sorte que les éléments
        inférieurs strictement à x soient au début.
        Retourne le plus petit indice k telle T[k] >= x
    """
    x = T[j - 1]
    u = i
    v = i
    while v < j - 1:
        # Invariant de boucle :
        # i <= w < u => T[w] < x
        # u <= w < v => T[w] >= x
        if T[v] < x:
            T[u], T[v] = T[v], T[u]
            u = u + 1
        v = v + 1
    T[u], T[j - 1] = T[j - 1], T[u]
    return u

T = [3, 6, 3, 1, 9, 2, 0, 4, 3]
partition(T, 0, len(T))
print(T)
[1, 2, 0, 3, 9, 6, 3, 4, 3]
In [ ]:
T = [3, 6, 3, 1, 9, 2, 0, 4, 3]
tri_rapide(T, 0, len(T))
print(T)
[0, 1, 2, 3, 3, 3, 4, 6, 9]

Complexité de la fonction tri_rapide

La boucle de la fonction partition(T, i, j) est exécutée $j-i$ fois. Cette fonction a donc une complexité linéaire en $j - i$.

L'efficacité de l'algorithme du tri rapide dépend du choix du pivot. Intuitivement, l'algorithme est d'autant plus performant que les pivots sont proches des valeurs médianes. La fonction partition partage alors chaque sous-tableaux en deux sous-tableaux qui ont approximativement la même taille. Le cas le plus pénalisant est celui où un tableau de taille $n$ donne un sous-tableau de taille $n-1$ et un sous-tableau de taille 0. Ceci se produit systématiquement lorsque le tableau de départ est déjà trié. Dans ce cas le coût $C(n)$ correspond au coût linéaire de la partition plus le coût du tri d'un tableau trié de taille $n-1$. Autrement dit $C(n)=na+C(n-1)$. Nous avons vu lors de l'analyse de la complexité du tri insertion récursif que cette formule de récurrence conduit à une complexité quadratique.

Ainsi, la complexité au pire du tri rapide est quadratique.

Plutôt que de choisir pour pivot le dernier élément du tableau, on peut décider de choisir ce pivot au hasard. On peut alors montrer que le coût moyen de la fonction tri_rapide est en $O(n\log n)$, autrement dit une complexité asymptotique aussi bonne que le tri fusion.

Amélioration de la fonction tri_rapide

Le code ci-dessous apporte les améliorations suivantes :

  • Le second et le troisième arguments de tri_rapide sont optionnels, ce qui simplifie l'utilisation de la fonction.
  • La fonction partition est définie localement.
  • Avant d'appeler la fonction partition le dernier élément est permuté avec un élément choisi au hasard. Ceci revient à choisir le pivot au hasard.
In [ ]:
from random import randint
# randint(a, b) retourne un entier r aléatoire tel que
# a <= r <= b
# Remarquez que b est inclus, contrairement à la convention
# python habituelle.

def tri_rapide(T, i=0, j=None):
    """ Trie en place la sous-liste T[i:j].  
    """
    
    def partition(T, i, j):
        """ Soit x = T[j - 1].
            Modifie T[i:j] de telle sorte que les éléments
            inférieurs strictement à x soient au début.
            Retourne le plus petit indice k telle T[k] >= x
        """
        x = T[j - 1]
        u = i
        v = i
        while v < j - 1:
            # Invariant de boucle :
            # i <= w < u => T[w] < x
            # u <= w < v => T[w] >= x
            if T[v] < x:
                T[u], T[v] = T[v], T[u]
                u = u + 1
            v = v + 1
        T[u], T[j - 1] = T[j - 1], T[u]
        return u 
    
    if j == None:
        j = len(T)
    if j - i > 1:
        r = randint(i, j - 1)
        T[r], T[j - 1] = T[j - 1], T[r]
        k = partition(T, i, j)
        tri_rapide(T, i, k)
        tri_rapide(T, k + 1, j)
        
T = [3, 6, 3, 1, 9, 2, 0, 4, 3]
tri_rapide(T)
print(T)
[0, 1, 2, 3, 3, 3, 4, 6, 9]

Complexité en moyenne de la fonction tri_rapide

On suppose que les $n!$ permutations possibles de $T$ sont équiprobables.

Le nombre d'opérations élémentaires est équivalent (dans le sens de la notation $\Theta$) au nombre de comparaisons effectuées sur les éléments de $T$.

Soit $X$ le nombre de comparaisons effectuées par l'algorithme. Il s'agit de calculer l'espérance de cette variable aléatoire $X$.

Soit $z_1, z_2, \dots, z_n$ les $n$ éléments de $T$ triés par ordre croissant.

Soit $X_{ij}$ le nombre de fois où $z_i$ et $z_j$ sont comparés entre eux.

$$X = \sum_{iet donc

$$E[X] = \sum_{iOn peut affirmer que :

  • Si $z_i$ et $z_j$ sont comparés entre eux alors l'un des deux a été choisi comme pivot.
  • Un élément ne peut pas être choisi plusieurs fois comme pivot.
  • $z_i$ et $z_j$ sont comparés au plus une fois.
  • $E[X_{ij}]$ est la probabilité que $z_i$ et $z_j$ soient comparés entre eux.
  • Soit $p$ le premier élément de $\{z_i, z_{i+1}, \dots, z_j\}$ à être choisi comme pivot.
    • Si $p=z_i$ ou $p=z_j$ alors $z_i$ et $z_j$ sont comparés
    • sinon $z_i$ et $z_j$ ne sont pas comparés par l'algorithme
  • $E[X_{ij}]=\frac{2}{j-i+1}$

On a donc

\begin{align} E[X] &= \sum_{i=1}^{n-1}\sum_{j=i+1}^{n} \frac{2}{j-i+1} \\ E[X] &= \sum_{i=1}^{n-1}\sum_{k=2}^{n-i+1} \frac{2}{k} \\ E[X] &<= 2\sum_{i=1}^{n-1}\sum_{k=2}^{n} \frac{1}{k} \\ E[x] &<= 2\sum_{i=1}^{n-1}\int_1^n\frac{dx}{x} \\ E[x] &<= 2\sum_{i=1}^{n-1}\ln n <= 2n\ln n \\ \end{align}

On voit ainsi que la complexité en moyenne du tri rapide est en $O(n\log n)$.

Optimalité de la complexité en $n\log n$

Supposons que nous disposions d'un algorithme pour trier une liste de valeurs. On suppose également que la seule action élémentaire possible sur ces valeurs est la comparaison de deux valeurs.

Nous pouvons représenter l'arbre de décision de cet algorithme. Voici un exemple d'arbre de décision possible pour le tri d'une liste de trois éléments :

Arbre de décision

Cet arbre signifie que l'algorithme choisit de comparer initialement le premier et le deuxième élément. Si le premier est plus petit ou égal au second alors il choisit ensuite de comparer le deuxième élément avec le troisième, sinon il compare le premier avec le troisième. L'algorithme continue ainsi à faire des choix jusqu'au moment où il considère avoir fini son travail.

Soit $n$ le nombre d'éléments de la liste. Soit $C(n)$ le nombre de comparaisons effectuées par l'algorithme dans le pire des cas. Nous affirmons qu'il existe une constante $a$ et un rang $n_0$ tels que $C(n)\geq an\log n$ pour tout $n\geq n_0$. Il s'agit donc ici d'une minoration asymptotique et non d'une majoration. On traduit cela par la notation $C(n)=\Omega(n\log n)$.

Démonstration :

soit $h$ la hauteur de l'arbre de décision et soit $f$ le nombre de feuilles. Dans l'exemple ci-dessus, $h=3$ et $f=6$.

Nous avons nécessairement $f\leq 2^h$. Les feuilles correspondent à une décision finale de l'algorithme quant à l'ordre des éléments de la liste. L'arbre de décision doit donc posséder au moins $n!$ feuilles. On a ainsi $n!\leq 2^h$. Dans le pire des cas, l'algorithme effectue exactement $h$ comparaisons. On a donc $C(n)\geq \log_2(n!)$.

La formule de Stirling :

$$n!\sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^n$$

prouve alors le résultat.