Quel pivot doit on prendre?
Peut on choisir des pivots efficaces dans tous les cas pratiques ? (vraisemblableent non!)
J'avais un vague souvenir selon lequel les tableau triés et "triés à l'envers" sont aussi défavorables les uns que les autres (en n²), mais c'est peut être une erreur...
Les droits inaliénables du troll :
1) le droit d'avoir raison
2) le droit d'être péremptoire
3) le droit de ne pas lire
4) le droit de ne pas répondre
5) le droit d'être de mauvaise foi
6) Autant pour moi / Faignant / Vivent Tintin et Milou
Tu peux prendre par exemple l'élément au milieu du tableau. Ou alors la méthode median-of-3 (le médian parmi le premier, le dernier et celui du milieu), qui règle à la fois le cas des tableaux triés à l'endroit et à l'envers. (Les cas défavorables en O(n²) existent évidemment toujours, mais sont plus complexes à construire.)
de toute façon, cf mon post en première page pour les cas moyens / pires cas ...
I'm on a boat motherfucker, don't you ever forget
