Tri rapide (Quicksort)
Définition :
Proposé par Tony Hoare en 1960, le tri rapide est un exemple de récursivité sur le résultat. La donnée initiale et le résultat sont les mêmes que pour le tri par fusion.
Cette opération s'appelle le partitionnement. Pour chacun des sous-tableaux, on définit un nouveau pivot et on répète l'opération de partitionnement. Ce processus est répété récursivement, jusqu'à ce que l'ensemble des éléments soit trié.
Diviser :
𝑇[𝑝. . 𝑟] est divisé en 2 sous-tableaux non vide 𝑇[𝑝. . 𝑞] et 𝑇[𝑞 + 1. . 𝑟] tel que : chaque élément de 𝑇[𝑝. . 𝑞] soit inférieur à chaque élément de 𝑇[𝑞 + 1. . 𝑟].
fonction Partitionner
Régner :
sous-tableaux triés grâce à la récursivité.
fonction 𝑇𝑟𝑖𝑅𝑎𝑝𝑖𝑑𝑒
Combiner : 2 sous-tableaux triés sur place : Rien à faire.
En pseudo-code, l'algorithme pourrait s'écrire ainsi (le pivot est l'élément le plus à gauche du
tableau) :
4 | 1 | 2 | 6 | 9 | 1 | 3 | 8 | 4 | 5 | 9 |
Deux pointeurs 𝑖, initialisé à 1, 𝑗 initialisé à 𝑡𝑎𝑖𝑙𝑙𝑒(𝑡𝑎𝑏)
Bouger 𝑖 vers la droite jusqu'à un élément 𝑠𝑢𝑝é𝑟𝑖𝑒𝑢𝑟 𝑎𝑢 pivot
Bouger 𝑗 vers la gauche jusqu'à un élément 𝑖𝑛𝑓é𝑟𝑖𝑒𝑢𝑟 𝑜𝑢 é𝑔𝑎𝑙 pivot
Échanger 𝑡𝑎𝑏[𝑖] et 𝑡𝑎𝑏[𝑗] et répéter tant que i < 𝑗
Échanger 𝑝𝑖𝑣𝑜𝑡 et 𝑡𝑎𝑏[𝑗]
