{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Le tri rapide\n", "\n", "Marc Lorenzi\n", "\n", "22 décembre 2018" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import matplotlib.pyplot as plt\n", "import random\n", "import math" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "plt.rcParams['figure.figsize'] = (10, 6)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 1 Introduction" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 1.1 Quicksort" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Le tri rapide (quicksort) est un algorithme permettant de trier des listes en pire cas en complexité $\\Theta(n^2)$ où $n$ est la longueur de la liste à trier. Malgré cette mauvaise complexité en pire cas, quicksort possède une complexité en moyenne en $\\Theta(n\\log n)$. De plus il possède le grand avantage de pouvoir trier les listes sur place, sans création de nouvelles listes. Sa \"constante cachée\" est relativement petite, ce qui en fait un algorithme de choix pour de nombreux problèmes où un tri s'avère nécessaire. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Avant de nous attaquer à quicksort, nous allons mettre en place quelques outils qui nous seront bien utiles." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 1.2 Un compteur d'opérations" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Nous allons parler de complexité, et donc compter des opérations. L'intérêt d'exposer un algorithme dans un notebook est que nous allons pouvoir confronter la belle théorie à la vile pratique ...\n", "\n", "Qu'allons nous compter ? Quicksort est un algorithme de tri __comparatif__, c'est à dire que pour trier une liste il compare entre-eux des éléments de la liste. Mais, me direz-vous, pour trier il faut bien comparer ! Point du tout. Il existe des algorithmes de tri qui ne comparent pas, mais ceci est un autre sujet. Qu'allons nous compter, dis-je ? Eh bien essentiellement des comparaisons d'éléments de listes. Et aussi, histoire de comparer (si j'ose dire), des échanges d'éléments de listes. Pour cela, il nous sera bien utile de posséder un compteur qui comptera à notre place. Plutot que de polluer le code de nos belles fonctions de tri avec des incrémentations de variables hors-sujet, voici une classe `Compteur` ... qui compte." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Un objet de la classe compteur possède deux champs, `comp` (compare) et `xch` (exchange). Ces deux champs contiennent des entiers qui sont incrémentés de 1 via les méthodes `incr_comp` et `incr_xch`. Un compteur peut aussi (heureusement) être réinitialisé via la méthode `reset`." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "class Compteur:\n", " \n", " def __init__(self):\n", " self.comp = 0\n", " self.xch = 0\n", " \n", " def incr_comp(self):\n", " self.comp += 1\n", " \n", " def incr_xch(self):\n", " self.xch += 1\n", " \n", " def reset(self):\n", " self.comp = 0\n", " self.xch = 0\n", " \n", " def __repr__(self):\n", " return 'comparaisons : %d\\nechanges : %d' % (self.comp, self.xch)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Nous allons définir un Compteur Global `CG` qui sera LE compteur utilisé dans tout le notebook." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "CG = Compteur()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Testons notre compteur.\n", "\n", "- On le réinitialise.\n", "- On incrémente 10000 fois l'un ou l'autre des champs du compteur, au hasard.\n", "- On affiche le compteur.\n", "- On le réinitialise.\n", "- On affiche le compteur (qui devrait être à zéro)." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "CG.reset()\n", "for k in range(10000):\n", " r = random.uniform(0, 1)\n", " if r < 0.5: CG.incr_comp()\n", " else: CG.incr_xch()\n", "print(CG)\n", "CG.reset()\n", "print(CG)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Tout va bien, notre compteur a l'air de fonctionner." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 1.3 Les opérations à compter" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Bien entendu, utiliser le compteur va nous obliger à un peu de discipline. Chaque fois que nous comparerons deux éléments $s[i]$ et $s[j]$ d'une liste, nous nous obligerons à appeler `inférieur(s, i, j)`, qui renvoie `True` si et seulement si $s[i]\\le s[j]$. " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def inferieur(s, i, j):\n", " CG.incr_comp()\n", " return s[i] <= s[j]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "CG.reset()\n", "s = [1, 4, 2, 3]\n", "print(inferieur(s, 1, 3))\n", "print(CG)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Et chaque fois que nous échangerons les éléments d'indices $i$ et $j$ de la liste $s$, notre devoir sera d'appeler `echanger(s, i, j)`." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def echanger(s, i, j):\n", " CG.incr_xch()\n", " s[i], s[j] = s[j], s[i]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "print(s)\n", "echanger(s, 1, 2)\n", "print(s)\n", "print(CG)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 1.4 Listes aléatoires" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Pour tester un algorithme de listes il est bon de pooséder une fonction renvoyant des listes aléatoires. La fonction ci-dessous prend un entier $n$ en paramètre et renvoie une permutation aléatoire de l'ensemble des entiers entre 0 et $n-1$. L'algorithme utilisé est celui de __Fisher-Yates__ : il renvoie toute liste avec une probabilité égale à $\\frac 1 {n!}$. Ce qui est heureux puisqu'il y a $n!$ permutations possibles.\n", "\n", "Remarquez que notre algorithme effectue 0 comparaison et $n$ échanges." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def liste_aleatoire(n):\n", " s = list(range(n))\n", " for i in range(n):\n", " j = random.randint(i, n - 1)\n", " echanger(s, i, j)\n", " return s" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "CG.reset()\n", "print(liste_aleatoire(10))\n", "print(CG)\n", "CG.reset()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 1.5 Une liste est-elle triée ?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Pour savoir si une liste est triée il n'y a qu'à regarder ? Sans doute, mais on s'usera les yeux quand nos listes auront un million d'éléments. Alors écrivons une fonction qui regarde pour nous.\n", "\n", "Une liste $[x_0,x_1,\\ldots,x_{n-1}]$ est triée si et seulement si pour tout $k = n - 1` permet au code de renvoyer la bonne valeur si la liste est vide (la liste vide est triée !)." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def est_triee(s):\n", " n = len(s)\n", " k = 0\n", " while k < n - 1 and s[k] <= s[k + 1]:\n", " k = k + 1\n", " return k >= n - 1" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "est_triee([1, 2, 3, 4, 5])" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "est_triee([1, 2, 4, 3, 5])" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "est_triee([])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 1.6 Statistiques" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Automatisons aussi nos futures statistiques sur quicksort (ou n'importe quel algorithme sur les listes qui compare ou qui échange). L'idée est simple. Étant donnée une fonction `algo` prenant une liste en paramètre, on exécute `algo` sur un certain nombre de listes (`sample`). On fait cela pour des tailles différentes. On renvoie pour chacune des tailles le nombre moyen de comparaisons et le nombre moyen d'échanges.\n", "\n", "- `min` est la taille minimale des listes testées.\n", "- `max` est la taille maximale des listes testées.\n", "- `step` est le pas permettant de passer d'une taille de liste à la suivante.\n", "\n", "Lisez le code, il ne présente aucune difficulté." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def stats(algo_tri, step=1, min=1, max =100, sample=1):\n", " tailles = list(range(min, max+step, step))\n", " temps_comp = []\n", " temps_xch = []\n", " for k in tailles:\n", " vcomp = 0\n", " vxch = 0\n", " for j in range(sample):\n", " s = liste_aleatoire(k)\n", " CG.reset()\n", " algo_tri(s)\n", " vcomp += CG.comp\n", " vxch += CG.xch\n", " temps_comp.append(vcomp / sample)\n", " temps_xch.append(vxch / sample)\n", " return (tailles, temps_comp, temps_xch)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Testons la fonction `stats` sur un algorithme idiot (?) qui ne trie certainement pas la liste. Mais bon, il compare et il échange ..." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def algo_idiot(s):\n", " for i in range(len(s) - 1):\n", " if inferieur(s, i, i + 1):\n", " echanger(s, i, i + 1)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "s = liste_aleatoire(20)\n", "print(s)\n", "CG.reset()\n", "algo_idiot(s)\n", "print(CG)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "stts = stats(algo_idiot, 1, 1, 100, 2)\n", "print(stts)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Ceci n'est pas très parlant, alors affichons un graphique." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "xs, ys, zs = stts\n", "plt.plot(xs, ys, 'k')\n", "plt.plot(xs, zs, 'r')\n", "plt.grid()\n", "plt.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "En noir, le nombre de comparaisons, qui ne devrait surprendre personne. Pour une liste de taille $n$, c'est $n-1$. Que le nombre d'échanges soit inférieur au nombre de comparaisons ne devrait pas non plus être une surprise." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 2 Le tri rapide" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 2.1 Le principe" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Quicksort est un algorithme du type __diviser pour régner__.\n", "\n", "Soit $s$ une liste à trier entre les indices minimal $l$ (left) et maximal $r$ (right). Si $l>r$ il n'y a rien à faire. Sinon, soit $x=s[r]$.\n", "\n", "1- On place dans la \"moitié\" gauche de la liste les éléments de $s$ inférieurs ou égaux à $x$.\n", "\n", "2- On place dans la \"moitié\" droite de la liste les éléments de $s$ strictement supérieurs à $x$.\n", "\n", "3- On trie la \"moitié\" gauche privée de x.\n", "\n", "4- On trie la \"moitié\" droite.\n", "\n", "Toutes ces opérations se passent bien entendu entre les indices $l$ et $r$. Remarquez également les guillemets autour du mot \"moitié\" : il n'y a aucune raison que les moitiés soient égales, nous devrions plutôt dire \"parties\". Mais j'aime bien l'idée des deux moitiés non égales.\n", "\n", "__Exercice__ : que valent les deux \"moitiés' lorsque la liste est déjà triée ?\n", "\n", "__Exercice__ : Quand les deux moitiés sont-elles exactement de même longueur ?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 2.2 Partitionner" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "La fonction ci-dessous effectue les opérations 1 et 2 dont je viens de parler. Un indice $i$ est mis à jour à l'intérieur d'une boucle indexée par un entier $j$.\n", "\n", "J'ai rajouté un paramètre `dbg` qui, mis à `True`, permet de visualiser les étapes de l'algorithme. Lorsque `dbg=True`, on affiche les valeurs de $i$, $j$ et $s$ à la fin de chaque itération." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def partition(s, l, r, dbg=False):\n", " i = l - 1\n", " for j in range(l, r):\n", " if inferieur(s, j, r):\n", " i = i + 1\n", " echanger(s, i, j)\n", " if dbg: print('i=%d, j=%d, s=%s'%(i, j, s))\n", " echanger(s, i + 1, r)\n", " return i + 1" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__Proposition__ : Soit $x=s[r]$. À l'issue de la $j$-ième itération ($l\\le j < r$) :\n", "\n", "- $i \\le j$\n", "- Tous les éléments de $s$ dont l'indice est compris entre $l$ et $i$ sont inférieurs ou égaux à $x$. \n", "- Tous les éléments de $s$ dont l'indice est compris entre $i+1$ et $j$ sont strictement supérieurs à $x$.\n", "\n", "__Démonstration__ : La preuve se fait par récurrence sur $j$.\n", "\n", "\n", "Ainsi, à l'issue de la dernière itération (celle où $j=r-1$, puisque `range(l, r)` $=[l,\\ldots,r-1]$ :\n", "\n", "- $i\\le r-1$.\n", "- Tous les éléments de $s$ dont l'indice est compris entre $l$ et $i$ sont inférieurs ou égaux à $x$. \n", "- Tous les éléments de $s$ dont l'indice est compris entre $i+1$ et $r-1$ sont strictement supérieurs à $x$.\n", "\n", "Reste à placer $s[r]$ au bon endroit. On l'échange avec $s[i+1]$ et on renvoie $i+1$. Est-ce une bonne idée ? Deux cas se présentent :\n", "\n", "- $ix$ et c'est donc une bonne idée.\n", "- $i=r-1$. Dans ce cas, on fait un échange inutile mais cela ne nuit pas." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Testons sans crainte, puisque la théorie nous dit que tout va bien. N'hésitez pas à évaluer la cellule ci-dessous un certain nombre de fois. Regardez les étapes de l'algorithme et comprenez ce qui se passe. Si on comprend `partition`, on comprend le tri rapide." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "N = 10\n", "s = liste_aleatoire(N)\n", "print(s)\n", "CG.reset()\n", "print('pivot : ', partition(s, 0, N - 1, dbg=True))\n", "print(s)\n", "print(CG)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 2.3 Nombre de comparaisons effectuées par `partition`" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__Proposition__ : Un appel à `partition(s, l, r)` effectue $n-1$ comparaisons, où $n=r-l+1$ est la taille de la sous-liste à partitionner.\n", "\n", "__Démonstration__ : Il suffit de compter le nombre d'itérations d'une boucle `for`. Le lecteur motivé devrait y arriver :-)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 2.4 Nombre d'échanges effectués par `partition`" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Si vous avez, comme je l'ai conseillé, exécuté la cellule précédente un certain nombre de fois vous avez dû remarquer que certains échanges (à chaque fois que $i$ est incrémenté) ne modifient pas la liste. C'est certes inefficace mais du coup il est évident de compter le nombre d'échages. Ne prenez surtout pas exemple sur moi, on ne rend pas une fonction inefficace pour pouvoir l'analyser plus facilement !\n", "\n", "On fait un échange à chaque fois que $i$ est incrémenté, c'est à dire à chaque fois qu'on rencontre un élément de la liste inférieur ou égal au pivot $x$. D'où la\n", "\n", "__Proposition__ : Un appel à `partition(s, l, r)` effectue $k$ échanges, où $k$ est le nombre d'éléments inférieurs ou égaux au pivot." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Quelles sont les valeurs possibles pour $k$ ? Eh bien, 1, 2, $\\ldots$, $n$, où $n=l-r+1$ est la taille de la sous-liste à partitionner. \n", "\n", "Quelle est la valeur \"moyenne\" de $k$ ? En admettant que les valeurs possibles pour $k$ sont uniformément réparties, c'est\n", "\n", "$$\\frac 1 n\\sum_{k=1}^n k=\\frac{n+1}2$$\n", "\n", "soit environ la moitié du nombre de comparaisons." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Pour illustrer tout cela, voici en rouge le nombre de comparaisons et ce nombre plus un divisé par deux, comme disaient les mathématiciens avant l'invention des symboles. Et en noir le nombre moyen d'échanges pour des échantillons de listes de diverses tailles." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "tailles, temps_comp, temps_xch = stats(lambda s:partition(s, 0, len(s) - 1), step=10, min=1, max=1000, sample=10)\n", "plt.plot(tailles, temps_comp, 'r')\n", "plt.plot(tailles, temps_xch, 'k')\n", "ys = [(x + 1) / 2 for x in tailles]\n", "plt.plot(tailles, ys, 'r')\n", "plt.grid()\n", "plt.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Notre valeur moyenne de $k$ dépasse nos espérances mathématiques." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 2.4 Trier" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "La fonction de tri est maintenant évidente.\n", "\n", "- `tri_aux` prend en paramètres une liste $s$ et deux indices $l$ et $r$. Elle trie la liste $s$ entre les indices $l$ et $r$ inclus.\n", "\n", "- `tri_rapide` trie toute la liste `s` en appelant `tri_aux` entre les indices 0 et `len(s)-1`." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def tri_aux(s, l, r):\n", " if l <= r:\n", " q = partition(s, l, r)\n", " tri_aux(s, l, q - 1)\n", " tri_aux(s, q + 1, r)\n", " \n", "def tri_rapide(s):\n", " tri_aux(s, 0, len(s) - 1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "La correction de la fonction `tri_rapide` se fait par récurrence forte sur la longueur des listes. Si `partition` fonctionne, `tri_rapide` aussi.\n", "\n", "__Exercice__ : Prouvez la correction de `tri_rapide`. Idée : que voulez vous prouver ?\n", "\n", "Testons sur un exemple (pléonasme)." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "s = liste_aleatoire(10)\n", "print(s)\n", "CG.reset()\n", "tri_rapide(s)\n", "print(s)\n", "print(CG)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Testons sur une __GROS__ exemple." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "s = liste_aleatoire(10000)\n", "#print(s)\n", "CG.reset()\n", "tri_rapide(s)\n", "print('Triée ?', est_triee(s))\n", "print(CG)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Avant de faire de jolis dessins, un peu de théorie ..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 2.4 La complexité en moyenne du tri rapide" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Notons $C_n$ le nombre moyen de comparaisons effectuées par `tri_rapide` sur une liste de taille $n$. Ne désirant pas entrer dans des détails probabilistes, je me contente de quelques explications pour \"établir\" une relation de récurrence sur les $C_n$.\n", "\n", "Soit à trier une liste $s$ de taille $n\\ge 1$. Un appel à `partition` effectue $n-1$ comparaisons. Puis la fonction `tri_aux` est appelée récursivement sur deux sous-listes $s_1$ et $s_2$ de $s$, l'une de taille $k$ et l'autre de taille $n-1-k$, où $0\\le k\\le n-1$. Toutes les valeurs de $k$ ont la même probabilité, à savoir $\\frac 1 n$. Admettons que la fonction `partition` ne perturbe pas les probabilités, c'est à dire que pour une valeur donnée de $k$ toutes les listes $s_1$ de taille $k$ ont la même probabilité d'apparaître (et de même pour les listes $s_2$ de taille $n-1-k$). On peut alors (je n'entre pas dans les détails) en déduire : \n", "\n", "$$\\forall n\\ge 1, \\ C_n=n-1+\\frac 1 n \\sum_{k=0}^{n-1}(C_k+C_{n-1-k})$$\n", "\n", "Comme, bien entendu, $C_0 = 0$, nous disposons d'une récurrence clés en main qu'il ne nous reste qu'à résoudre.\n", "\n", "__Exercice__ : Que vaut $C_1$ ? Que vaut $C_2$ ? Que vaut $C_3$ ? Bon j'arrête :-).\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Soit $n\\ge 1$. Commençons par remarquer (changement d'indice $k'=n-1-k$) que $\\sum_{k=0}^{n-1}C_{n-1-k}=\\sum_{k=0}^{n-1}C_k$.\n", "\n", "On a donc $C_n=n-1+\\frac 2 n \\sum_{k=0}^{n-1}C_k$, d'où \n", "\n", "$$nC_n=n(n-1)+2\\sum_{k=0}^{n-1}C_k$$\n", "\n", "De là, pour $n\\ge 2$, $nC_n-(n-1)C_{n-1}=n(n-1)-(n-1)(n-2)+2C_{n-1}=2(n-1)+2C_{n-1}$, et donc\n", "\n", "$$nC_n=2(n-1)+(n+1)C_{n-1}$$\n", "\n", "Remarquons que cette égalité reste valable pour $n=1$, puisque $C_0=C_1=0$. Divisons par $n(n+1)$. Nous obtenons, pour tout $n\\ge 1$, \n", "\n", "$$\\frac{C_n}{n+1}=\\frac{C_{n-1}}{n}+2\\frac{n-1}{n(n+1)}$$\n", "\n", "Une simple récurrence montre alors que\n", "\n", "$$\\frac{C_n}{n+1}=2\\sum_{k=1}^n\\frac{k-1}{k(k+1)}$$\n", "\n", "Poursuivons en décomposant les fractions en éléments simples : $\\frac{C_n}{n+1}=2\\sum_{k=1}^n(\\frac{-1}k + \\frac 2 {k+1})=2H_{n+1}-4+\\frac 2 {n+1}$ où $H_n=\\sum_{k=1}^n \\frac 1 k$ est le $n$ième nombre harmonique. Rappelons le résultat bien connu (ou pas)\n", "\n", "$$H_n=\\ln n+\\gamma + O(\\frac 1 n)$$\n", "\n", "où $\\gamma\\simeq 0.577216$ est la constante d'Euler. On en déduit la\n", "\n", "__Proposition__ : \n", "\n", "- Pour tout $n\\ge 0$, $C_n=2(n+1)H_{n+1}-4(n+1)+ 2$.\n", "- $C_n = 2(n+1)\\ln(n+1) +(2\\gamma-4)(n+1) + O(1)$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__Exercice__ : Euh, ça marche aussi pour $n=0$ ? Vérifiez." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Comme annoncé dans l'introduction, la complexité moyenne du tri rapide est donc $\\Theta(n\\log n)$, où $n$ est la longueur de la liste à trier." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def complexite_theo(n):\n", " ga = 0.577215664\n", " return 2 * (n + 1) * math.log(n + 1) + (2 * ga - 4) * (n + 1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 2.5 Statistiques" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Réconcilions théorie et pratique sur un même graphique. En rouge, la complexité moyenne théorique. En noir, le nombre de comparaisons constatées sur des tests." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "tailles, temps_comp, temps_xch = stats(tri_rapide, step=10, min=0, max=1000, sample=3)\n", "plt.plot(tailles, temps_comp, 'k')\n", "#plt.plot(tailles, temps_xch, 'b')\n", "ys = [complexite_theo(k) for k in tailles]\n", "#zs = [(k+1)*(math.log(k+1)+0.577215+1/(2*(k+1))-1) for k in tailles]\n", "plt.plot(tailles, ys, 'r')\n", "#plt.plot(tailles, zs, 'r')\n", "plt.grid()\n", "plt.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Ça fait plaisir à voir." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 2.6 L'écart-type du tri rapide" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Savoir que le tri rapide est rapide en moyenne c'est bien. Mais cela ne prouve pas qu'il se comporte bien tout le temps. Une mesure intéressante d'une variable aléatoire, outre son espérance, est son écart-type. Un petit écart-type indique des valeurs de la variable aléatoire \"resserrées\" autour de sa moyenne. Alors, quel est l'écart-type du quicksort ?\n", "\n", "__Proposition__ : L'écart-type du tri rapide pour des listes de taille $n$ est\n", "\n", "$$\\sigma_n \\sim n\\sqrt{7-\\frac 2 3 \\pi^2}\\simeq 0.648 n$$ \n", "\n", "__Démonstration__ : Bien au delà des ambitions de ce notebook. Contentons-nous de remarquer que $\\sigma_n=o(C_n)$ : l'écart-type est __négligeable__ devant la moyenne ! Retraçons le graphique ci-dessus en y rajoutant deux courbes en pointillés, correspondant à moyenne $\\pm$ écart-type." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "math.sqrt(7 - 2 * math.pi ** 2 / 3)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "tailles, temps_comp, temps_xch = stats(tri_rapide, step=1, min=400, max=500, sample=5)\n", "plt.plot(tailles, temps_comp, 'k')\n", "#plt.plot(tailles, temps_xch, 'b')\n", "ys = [complexite_theo(k) for k in tailles]\n", "zs1 = [complexite_theo(k) - 0.648 * k for k in tailles]\n", "zs2 = [complexite_theo(k) + 0.648 * k for k in tailles]\n", "plt.plot(tailles, ys, 'r')\n", "plt.plot(tailles, zs1, 'b--')\n", "plt.plot(tailles, zs2, 'b--')\n", "plt.grid()\n", "plt.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "C'est presque trop beau pour être vrai. L'introduction du notebook annonçait un pire cas du tri rapide en $\\Theta(n^2)$. Comment est-il possible que nous n'ayons pas sur notre graphique un ou deux points complètement gagas, correspondant à des listes sur lesquelles le comportement du tri est très mauvais ? Eh bien de telles listes sont TRÈS TRÈS rares. Si vous vous ennuyez, évaluez encore et encore la cellule ci-dessus et appelez-moi dès que vous verrez un point bizarre :-)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 3 Compléments" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 3.1 La complexité en pire cas du tri rapide" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Oui, le tri rapide peut se comporter très mal. Et le problème c'est que cela arrive dans la vraie vie. Nous allons étudier la complexité en pire cas du tri rapide, et montrer que cette complexité est atteinte pour les listes déjà triées. C'est très ennuyeux parce qu'il s'avère que dans les applications réelles on a souvent à trier des listes __presques__ triées. D'où un comportement catastrophique du quicksort. Nous verrons dans la section suivante commment remédier à cela au moyen d'une __randomisation__ (anglicisme navrant)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Notons $C(s)$ le nombre de comparaisons d'éléments de listes effectuées par un appel à `tri_rapide(s, 0, len(s) - 1)`. Notons également $C_n=\\max\\{C(s), |s|= n\\}$ le nombre maximal de comparaisons effectuées par `tri_rapide` sur les listes de longueur $n$.\n", "\n", "On a $C_0=0$. Soit $n\\ge 1$. Soit $s$ une liste de longueur $n$. On a \n", "\n", "$$C(s)=n-1+C(s_1) + C(s_2)$$\n", "\n", "où $s_1$ et $s_2$ sont les listes sur lesquelles la fonction de tri se rappelle récursivement. Soit $k=|s_1|$. On a $0\\le k\\le n - 1$ et donc $C(s_1)\\le C_k$. Bien entendu, $|s_2|=n-1-k$, et donc $C(s_2)\\le C_{n-1-k}$. Ainsi, \n", "\n", "$$C(s)\\le n-1 + C_k+C_{n-1-k}$$\n", "\n", "où le $n-1$ est le nombre de comparaisons effectuées par la fonction de partition. De là, $C(s)\\le n-1+\\max\\{C_k+C_{n-1-k}, 0\\le k\\le n-1\\}$. Ceci étant vrai pour toute liste de longueur $n$, on en déduit\n", "\n", "$$\\forall n\\ge 1,C_n\\le n-1 + \\max\\{C_k+C_{n-1-k}, 0\\le k\\le n-1\\}$$\n", "\n", "__Proposition__ : Pour tout $n\\in\\mathbb N$, $C_n\\le \\frac 1 2 n(n - 1)$.\n", "\n", "__Démonstration__ : On fait une récurrence forte sur $n$. Pour $n=0$ c'est clair puisque $C_0=0$. Soit $n\\ge 1$. Supposons l'inégalité vraie pour tous les entiers $0\\le k