Algorithme du tri rapide

En utilisant des list comprehension de python, le code est plus compacte et plus clair que sa version en pseudocode :

def rapide(T):
    if len(T) <= 1:
        return list(T)

    pivot = T[0]

    T1 = [T[i] for i in range(1, len(T)) if T[i] <= pivot]
    T2 = [T[i] for i in range(1, len(T)) if T[i] > pivot]

    return rapide(T1) + [pivot] + rapide(T2)

Les list comprehension sont un moyen clair et efficace de générer des listes. Utilisez-les !

La complexité maximale va arriver si un des deux tableaux est toujours vide. Par exemple lorsque le tableau est déjà trié.

Pour des tableaux triés, T1 ou T2 est vide et l'autre tableau est de taille $n-1$, ce qui donne une complexité de :

Et donc :

$$ C_{\max}(n) = \Theta(n^2) $$

Formellement, nous ne venons que de montrer que $C(n) = \Omega(n^2)$ puisque l'on a pas prouvé que les tableaux triés étaient le cas le pire. Pour conclure la preuve, il nous reste à montrer que $C(n) = \mathcal{O}(n^2)$.

Faisons-le par récurrence en prouvant qu'il existe $K$ tel que $C(n) \leq K \cdot n^2$ pour tout $n\geq 1$. Cette hypothèse est trivialement vraie pour $n=1$ et supposons la vraie pour $n-1$. Examinons le cas $n$ :

Notre hypothèse est démontrée.

On a finalement l'encadrement : $\Theta(n^2) = C_{\max}(n) = \mathcal{O}(n^2)$, ce qui nous permet de conclure que la complexité (maximale) du tri rapide pour un tableau de taille $n$ est $\Theta(n^2)$.

Comme $C(n)$ est une fonction croissante et que $C(n) \geq \mathcal{O}(n)$, la complexité de l'algorithme croit de façon linéaire ou plus. Si la forme de $C(n)$ est sans point d'inflexion, au moins asymptotiquement, la courbe de complexité sera au-dessus de sa tangente : c'est une fonction convexe.

On a alors $C_{\min}(\frac{n}{k}) + C_{\min}(\frac{(k-1)n}{k}) \geq 2\cdot C_{\min}(\frac{n}{2})$. Il sera donc toujours plus intéressant de couper notre tableau en 2 exactement. Dans ce cas là, on a l'équation de récurrence : $C_\min(n) = \mathcal{O}(n) + 2 \cdot C_\min(\frac{n}{2})$ et la preuve de l'algorithme fusion nous permet de conclure que :

$$ C_{\min(n)} = \mathcal{O}(n\ln(n)) $$

Faisons la preuve de complexité rigoureusement.

Pour chaque exécution de l'algorithme, on crée (au maximum) deux tableaux à partir du tableau $T$ passé en paramètre. On peut ranger ces créations par étage, comme le montre la figure suivante :

On lance l’algorithme à l'étage 0 avec $T_0$ comme tableau originel. Ce tableau crée (au maximum) les tableaux $T_1$ et $T_2$ à l'étage 1 qui eux-même vont créer d'autres tableaux qui formeront l'étage 2 et ainsi de suite.

Chaque tableau $T_i$ crée donc soit :

• 0 tableau
• 1 tableau nommé $T_{2\cdot i}$
• 2 tableaux nommés $T_{2\cdot i}$ et $T_{2\cdot i + 1}$

L'étage $k>1$ est ainsi formé d'au plus $2^{k-1}$ tableaux, allant des tableaux allant des indices $(\sum_{0\leq i \leq k - 2}2^i) +1$ à $(\sum_{0\leq i \leq k-1}2^i)$.

Comme chaque exécution de l'algorithme hors récursion est proportionnelle à la taille du tableau en entrée, la complexité totale de l'exécution de toutes les récursion de l'algorithme sera proportionnelle à la somme des tailles des tableaux qui la composent (le tableau de $T_i$ ayant $n_i$ éléments) :

La complexité minimale sera atteinte pour la plus petite somme de $n_i$.

Chaque élément est compté 1 fois pour chaque tableau qui le compose. Comme l'ensemble des tableaux ayant un élément $x$ donné forme un chemin allant de $T_1$ à un tableau $T_i$ pour lequel $x$ est choisi comme pivot. En notant $e(x)$ l'étage pour lequel l'élément $x$ de $T_0$ a été choisi comme pivot, la complexité $C$ de l'algorithme vaut alors également :

La complexité minimale va donc être atteinte pour des arbres les plus tassés possibles puisqu'un élément $x$ choisi tard comme pivot aura un $e(x)$ plus important qu'un élément choisi plus tôt comme pivot. Comme chaque arbre de chaque étage produit 1 pivot on en conclut que :

La complexité minimale est atteinte si chaque étage $k$ est constitué du nombre maximum d'arbres, c'est à dire $2^k$.

Comme le nombre total d'arbre vaut $n$ on en déduit que pour les arbres réalisant la complexité minimale, on a :

La hauteur minimale de l'arbre est donc atteinte pour $K \simeq \log_2(n)$ avec des rangées pleines. Cet arbre minimisera effectivement $C = \mathcal{O}(\sum_{x \in T_0}e(x))$ puisque toutes les couches minimales seront prises. Pour cet arbre on aura $K=\log_2(n)$ et :

On a utilisé le fait que $\sum_{1 \leq k \leq K}k\cdot 2^{k-1} = (K-1)2^{K} + 1$ (on le démontrera).

on utilise l'argument utilisé pour calculer la complexité en moyenne du tri par insertion. Si le tableau suit le modèle aléatoire, la moitié de T[1:] est plus grande que T[0]. De là, en moyenne, on va toujours couper le tableau en 2 parties (plus ou moins) égales.

Si l'on coupe toujours au milieu on a alors la même équation que pour la complexité minimale : $C(n) = \mathcal{O}(n) + 2 \cdot C(\frac{n}{2})$, ce qui donne une complexité de $\mathcal{O}(n\ln(n))$.

Il faut résoudre l'équation :

où $p_i$ est la probabilité que le pivot soit le $i+1$ plus petit élément du tableau. On suppose pour cela que notre tableau suit le modèle aléatoire et donc que $p_i = \frac{1}{n}$ pour tout $i$.

Pour éviter de nous trimballer des $\mathcal{O}(n)$ partout, on va considérer que l'on y effectue $K\cdot n$ opérations où $K$ est une constante. On peut alors écrire :

On peut simplifier cette écriture en remarquant que :

• $\sum_{0 \leq i < n}C_{\mbox{moy}}(i) = \sum_{1 \leq i \leq n}C_{\mbox{moy}}(i-1)$
• $\sum_{0 \leq i < n}C_{\mbox{moy}}(n-i-1) = \sum_{1 \leq i \leq n}C_{\mbox{moy}}(i-1)$

On doit donc résoudre l'équation :

Il va maintenant y avoir 2 astuces coup sur coup. La première astuce est de considérer l'équation $n\cdot C_{\mbox{moy}}(n) - (n-1)\cdot C_{\mbox{moy}}(n-1)$ qui va nous permettre d'éliminer la somme :

On en déduit :

Et maintenant la seconde astuce : on divise l'équation ci-dessus par $n(n+1)$ pour obtenir un terme générique identique des deux côtés de l'équation :

$$ \frac{C_{\mbox{moy}}(n)}{n+1}=\frac{C_{\mbox{moy}}(n-1)}{n} + K\cdot\frac{2n - 1}{n(n+1)} $$

On peut alors poser $A(n) = \frac{1}{n+1} \cdot C_{\mbox{moy}}(n)$ et on doit maintenant résoudre :

$$ A(n) = A(n-1) + K\cdot\frac{2n - 1}{n(n+1)} $$

Ce qui donne :

On peut facilement montrer (on le démontrera) que $\sum_{i=1}^{n}\frac{1}{i(i+1)} = \frac{n}{n+1} = \mathcal{O}(1)$ et donc que :

La suite $A(n)$ se comporte comme un $\mathcal{O}(H(n))$ où $H(n) = \sum_{i=1}^{n}\frac{1}{i}$.

Cette fonction est connue, elle s'appelle la série harmonique, et est équivalente à $\ln(n)$ lorsque $n$ tend vers $+\infty$ (ça aussi, on le démontrera). On a alors que $\mathcal{O}(H(n)) = \mathcal{O}(\ln(n))$, et enfin :

$$ A(n) = \mathcal{O}(\ln(n)) $$

Qui en revenant aux $C_{\mbox{moy}}(n) = n\cdot A(n)$ donne :

$$ C_{\mbox{moy}}(n) = \mathcal{O}(n\ln(n)) $$

ouf.

La complexité en moyenne du tri rapide pour un tableau de taille $n$ est $\mathcal{O}(n\ln(n))$