L'étude est un peu subtile, et le lemme important et qu'en partant de permutations équiprobables, on arrive après la phase de division du tableau à des permutations des tableaux restant à trier qui sont encore équiprobables, ce qui est rarement bien fait dans les livres d'algorithmique…
L'algorithme présenté dans le Beauquier n'est pas le tri rapide de base, c'est pour ça qu'on se base sur celui présenté dans le Cormen et qu'on adapte la preuve du Beauquier pour calculer la complexité en moyenne du tri rapide.
Références utilisées dans les versions de ce développement :
Eléments d'algorithmique, Beauquier, Berstel et Chrétienne (utilisée dans 11 versions au total) Introduction à l'algorithmique, Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest (utilisée dans 49 versions au total)
Connexion
Inscription
Confirmer la suppresion
Attention, ce développement est utilisé dans des leçons de votre couplage. Voulez-vous quand même le supprimer de votre couplage ?
Notre livre est édité !
Après plus d'un an et demi d'écriture, notre livre voit enfin le jour !
Cet ouvrage a été relu par des agrégatifs comme vous pour en faire un outil le plus utile possible !
Cet ouvrage propose une liste de développements analysés finement, replacés dans un contexte global listant le plus exhaustivement possible les imbrications des résultats avec le reste du monde mathématique. Le lecteur trouvera dans cet ouvrage toute les techniques fondamentales de preuve ainsi que des entraînements complets et pédagogiques afin d’être préparé au mieux pour le concours de l’agrégation de mathématiques.