Recherche:

Oui le pire des cas est en n^2, mais en O(n) avec une forte probabilité si le pivot est choisi au hazard.

Dans tous les cas on ne peut pas faire plus vite que la dernière méthode, pour un faible...

Comme j'ai eu un peu de mal à trouver des informations sur la recherche rapide de médiane, je récapitule ici ce que j'ai trouvé.

Soit n valeurs
Soit Tab le tableau contenant ces valeurs.

...