24. Quick Sort : Partitionnement et Récursivité (Partie 2)

Le Schéma de Partition de Lomuto (Simplifié)

1. Sélectionner le dernier élément comme pivot.
2. Utiliser un index i (commençant au premier élément) pour suivre où se termine la limite des éléments 'plus petits'.
3. Itérer à travers le tableau j :
   • Si arr[j] est inférieur ou égal au pivot, échanger arr[i] et arr[j], et incrémenter i.
4. Enfin, échanger le pivot dans la position i.

Analyse de l'Efficacité

• Temps du Cas Moyen : O(N log N). Ceci est très efficace et généralement plus rapide en pratique que le Merge Sort en raison de meilleurs facteurs constants (il utilise moins d'accès mémoire).
• Temps du Pire Cas : O(N²).
  • Cela se produit si la sélection du pivot est constamment mauvaise (par exemple, choisir toujours l'élément le plus petit ou le plus grand), conduisant à des partitions déséquilibrées (un sous-tableau de taille N-1 et un de taille 0). C'est rare avec de bonnes stratégies de sélection de pivot (comme le « median-of-three » ou le pivot aléatoire).