Qual é a vantagem do Randomized Quicksort?

Em seu livro Randomized Algorithms , Motwani e Raghavan abrem a introdução com uma descrição de sua função RandQS - quicksort randomized - onde o pivô, usado para particionar o conjunto em duas partes, é escolhido aleatoriamente.

Há muito tempo que estou atormentando meus cérebros (reconhecidamente pouco potentes), mas não consigo ver que vantagem esse algoritmo tem sobre simplesmente escolher, digamos, o elemento do meio (no índice, não no tamanho) a cada vez.

Suponho que o que não vejo é o seguinte: se o conjunto inicial estiver em uma ordem aleatória, qual é a diferença entre escolher um elemento em um local aleatório no conjunto e escolher um elemento em uma posição fixa?

Alguém pode me esclarecer, em termos bastante simples?

Se a matriz de entrada é distribuída uniformemente aleatoriamente, então (como você observou), não há diferença entre sempre escolher um elemento em uma posição fixa (por exemplo, o meio como você sugere) ou escolher um elemento escolhido aleatoriamente.

Se, no entanto, sua matriz de entrada não estiver realmente em ordem aleatória (o que acontece em quase todos os cenários práticos), será necessário "pré-ordenar" a matriz para que os elementos nela sejam colocados em ordem aleatória ou ( equivalentemente) sempre use um elemento aleatório como um pivô. Isso garante que a fase de particionamento das partições de quicksort as matrizes em sub-matrizes de tamanho quase igual e, portanto, o tempo de execução esperado permaneça $O(n\log n)$

Portanto, sua confusão parece vir do fato de que, de alguma forma, você assume que um algoritmo de classificação pode (na prática) esperar que a matriz de entrada seja sempre distribuída aleatoriamente.

Como observado por Jernej, a suposição de que todas as permutações da entrada são igualmente prováveis ​​nem sempre é válida. A primeira idéia pode ser permutar a matriz de entrada. Isso funcionaria, mas é mais fácil analisar a situação em que um pivô é escolhido aleatoriamente. Isso também é conhecido como amostragem aleatória .