Fondations mathématiques de tri : Dériver Comparaisons et Swaps attendus dans Quicksort
Quicksort est un algorithme de tri largement utilisé connu pour son efficacité. Comprendre sa performance implique d'analyser le nombre attendu de comparaisons et d'échange pendant l'exécution. Cet article explore les principes mathématiques derrière ces attentes, en se concentrant sur l'analyse probabiliste de Quicksort.
Nombre prévu de comparaisons
Le nombre de comparaisons attendu dans Quicksort dépend du choix du pivot et du processus de partitionnement. En supposant que toutes les permutations sont également probables, le cas moyen peut être analysé à l'aide d'équations récursives. Pour un tableau de taille n], les comparaisons attendues, désignées comme C(n), satisfont la récurrence:
C(n) = n - 1 + frac{1}{n} sum {k=0}^{n-1} [C(k) + C(n - 1 - k)]
Cette récurrence simplifie un résultat bien connu : C(n) -2n ln n pour les grandes n. La dérivation consiste à résumer toutes les positions possibles de pivot et à appliquer les propriétés des nombres harmoniques.
Nombre prévu d'échanges
Les swaps dans Quicksort se produisent pendant le processus de partitionnement. Le nombre prévu de swaps est lié au nombre de comparaisons et à la distribution des choix de pivot. Sous un randomisme uniforme, les swaps attendus, désignés comme S(n), peuvent être approchés en analysant les étapes de partitionnement.
Chaque étape de partition implique l'échange d'éléments pour assurer un positionnement correct du pivot. Les swaps prévus par partition sont proportionnels à la taille des sous-arrays. Le résumé de tous les appels récursifs donne une approximation: S(n) ↓ n ln n.
Résumé des attentes
- Comparaisons:[ Environ 2n ln n pour les grandes n.
- Swaps: Environ n ln n pour les grandes n.
- Les deux métriques se développent logarithmiquement avec la taille du tableau, reflétant l'efficacité de Quicksort.