∑
MathTCG
#011 / 100•Space, Chance & Computation•MathTCG #411 / 500•★★★★Épique•⊦Maths Discrètes•Méthode & Idée

Algorithme de tri rapide

Période historique : 1959

Quicksort : le paradigme du diviser pour régner partitionnant récursivement autour d'un pivot.

Contenu & Formulation mathématique

Principe de la démarche
Quicksort : le paradigme du diviser pour régner partitionnant récursivement autour d'un pivot.
Champs d'application canoniques
Démonstration mathématique
T(n)=2T(n/2)+Θ(n)  ⟹  Tmoyen(n)=2nln⁡n+O(n)∼1.386nlog⁡2nT(n) = 2T(n/2) + \Theta(n) \implies T_{moyen}(n) = 2n \ln n + \mathcal{O}(n) \sim 1.386 n \log_2 n

Genèse & Portée historique

Inventé par Tony Hoare en 1959, Quicksort partitionne un tableau autour d'un élément pivot de sorte que les éléments inférieurs soient à gauche et les supérieurs à droite, puis se rappelle récursivement sur chaque partition. Sa complexité moyenne est optimale en O(n log n) avec une constante multiplicative exceptionnellement basse et un tri sur place.

Hoare cherchait à trier des mots en mémoire pour une traduction automatique du russe vers l'anglais au National Physical Laboratory lorsqu'il imagina cette partition récursive foudroyante.

« Choisir un pivot, séparer les mondes, et laisser la récursion accomplir l'ordre. »

Filiations & Relations conceptuelles (1)

Établi / Formulé par#462

C. A. R. Hoare

Quicksort a été inventé par Tony Hoare en 1959.

Objet de collection MathTCG

#411
★★★★Épique
⊦

Algorithme de tri rapide

Maths Discrètes•MÉTHODE

Principe : Quicksort : le paradigme du diviser pour régner partitionnant récursivement autour d'un pivot.

T(n)=2T(n/2)+Θ(n)  ⟹  Tmoyen(n)=2nln⁡n+O(n)∼1.386nlog⁡2nT(n) = 2T(n/2) + \Theta(n) \implies T_{moyen}(n) = 2n \ln n + \mathcal{O}(n) \sim 1.386 n \log_2 n
1959

Dans l'édition physique et numérique de MathTCG, cette carte appartient à l'extension Space, Chance & Computation.

Extension : Space, Chance & Computation (#011 / 100)
Numéro global MathTCG : MathTCG #411 / 500
Rareté officielle : Épique (★★★★)
Domaine théorique : Maths Discrètes
Identifiant pérenne : algorithme-de-tri-rapide
Consulter mon classeurExplorer tout le recueil