Développement : Complexité moyenne du tri rapide

Détails/Enoncé :

On établit la complexité $O(n\log(n))$ du tri rapide _déterministe_.

Recasages pour l'année 2025 :

  • Pas de recasages pour cette année.

Versions :

  • Auteur :
  • Remarque :
    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…
  • Référence :

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)