{"cells": [{"cell_type": "markdown", "metadata": {}, "source": ["# 1A.algo - Quicksort\n", "\n", "Cet \u00e9nonc\u00e9 a pour objectif de pr\u00e9senter l'algorithme de tri [quicksort](https://fr.wikipedia.org/wiki/Tri_rapide) qui permet de trier par ordre croissant un ensemble d'\u00e9l\u00e9ments (ici des cha\u00eenes de caract\u00e8res) avec un co\u00fbt moyen."]}, {"cell_type": "markdown", "metadata": {}, "source": ["Lorsqu'on parle de co\u00fbt moyen, cela signifie que le co\u00fbt n'est pas constant en fonction de la dimension du probl\u00e8me. Ici, le co\u00fbt moyen d\u00e9signe le co\u00fbt moyen d'un tri \\textit{quicksort} obtenu en faisant la moyenne du co\u00fbt du m\u00eame algorithme sur toutes les permutations possibles de l'ensemble de d\u00e9part. en $O(n \\ln n)$ o\u00f9 $n$ est le nombre d'\u00e9l\u00e9ments \u00e0 classer. Le tri *quicksort* appara\u00eet rarement sous la forme d'un graphe : il est plus simple \u00e0 programmer sans les graphes mais il est plus simple \u00e0 appr\u00e9hender avec les graphes. Dans cette derni\u00e8re version, l'algorithme ins\u00e8re un \u00e0 un les \u00e9l\u00e9ments d'une liste \u00e0 trier dans un graphe. Chaque noeud de ce graphe est reli\u00e9 \u00e0 deux autres noeuds."]}, {"cell_type": "markdown", "metadata": {}, "source": ["* Un noeud ``avant`` ou ``\"<\"`` qui permet d'acc\u00e9der \u00e0 des \u00e9l\u00e9ments class\u00e9s avant celui de ce noeud.\n", "* Un noeud ``apres`` ou ``\">\"`` qui permet d'acc\u00e9der \u00e0 des \u00e9l\u00e9ments class\u00e9s apr\u00e8s celui de ce noeud.\n"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Les noeuds ``avant`` et ``apres`` sont appel\u00e9s les successeurs. Le terme oppos\u00e9 est pr\u00e9d\u00e9cesseur. Ces deux noeuds ont n\u00e9cessairement un pr\u00e9d\u00e9cesseur mais un noeud n'a pas forc\u00e9ment de successeurs. S'il en avait toujours un, l'arbre serait infini."]}, {"cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [{"data": {"text/html": ["
\n", ""], "text/plain": ["