Quel est l'avantage de Randomized Quicksort?

Dans leur livre Randomized Algorithms , Motwani et Raghavan ouvrent l'introduction avec une description de leur fonction RandQS - Randomized quicksort - où le pivot, utilisé pour partitionner l'ensemble en deux parties, est choisi au hasard.

J'ai accumulé mes cerveaux (certes un peu sous-alimentés) pendant un certain temps, mais je n'ai pas pu voir quel avantage cet algorithme a par rapport au simple choix, disons, de l'élément central (en index, pas en taille) à chaque fois.

Je suppose que ce que je ne vois pas est le suivant: si l'ensemble initial est dans un ordre aléatoire, quelle est la différence entre choisir un élément à un endroit aléatoire dans l'ensemble et choisir un élément à une position fixe?

Quelqu'un peut-il m'éclairer, en termes assez simples?

Si le tableau d'entrée est distribué uniformément au hasard, alors (comme vous l'avez noté) il n'y a pas de différence entre toujours choisir un élément à une position fixe (par exemple, celui du milieu comme vous le suggérez) ou choisir un élément choisi au hasard.

$O(n\log n)$

Ainsi, votre confusion semble provenir du fait que, d'une manière ou d'une autre, vous supposez qu'un algorithme de tri peut (en pratique) s'attendre à ce que le tableau d'entrée soit toujours distribué de manière aléatoire.

Comme l'a noté Jernej, l'hypothèse selon laquelle toutes les permutations de l'entrée sont également probables ne tient pas toujours dans la réalité. La première idée pourrait être de permuter le tableau d'entrée. Cela fonctionnerait, mais il est plus facile d'analyser la situation où un pivot est choisi au hasard. Ceci est également connu sous le nom d' échantillonnage aléatoire .