Quick-Sort Randomized é o Quick-Sort (já citado) mas com uma alteração fundamental, a desvatagem do anterior era uma divisão desbalanceada do arranjo, mas agora com essa nova abordagem ela irá ocorrer muito raramente. Esta mudança é devida a divisão do arranjo agora ser feita de maneira aleatória, para mais detalhes recomendamos a leitura do capítulo 7 do livro Algoritmos (Cormen, 2002).

Confira o Código Fonte em C/C++!

Complexidade
Melhor Caso: Θ(n lg n);
Caso Médio: Θ(n lg n);
Pior Caso: Raramente Θ(n²).

Testes
A intenção de realizar esses testes para a versão aleatória do Quick-Sort é de verificar se a mudança na divisão do arranjo irá influenciar realmente no tempo de execução do algoritmo.

A figura mostra um gráfico do comportamento do Quick-Sort Random no pior caso. Eixo Vertical: segundos de 0 à 1, Eixo Horizontal: número de elementos de 100.000 à 2.000.000.

Não deixe de conferir o Quick-Sort (Não Randômico)!