Estou tentando entender por que o quicksort usando a partição Lomuto e um pivô fixo está executando de maneira incorreta, mas de maneira geral ruim, em entradas geradas aleatoriamente. Estou pensando que, embora as entradas sejam geradas aleatoriamente, pode haver muita ordem para as seqüências, mas não tenho certeza de como medir o nível de desordem nas seqüências. Pensei em usar o número de inversões, mas vi nessa outra pergunta que perguntei que não é realmente uma boa medida nesse caso.
A razão pela qual suspeito que minhas seqüências aleatórias têm muita "ordem" para elas é que a randomização do pivô corrige o problema de desempenho. Mas teoricamente não deve haver nenhum problema de desempenho nessas seqüências de entrada supostamente "aleatórias".
fonte
Respostas:
Partição Lomuto vs Hoare Lomuto sofre ao classificar chaves iguais, enquanto a partição Hoare não.
Ambos os esquemas de partição sofrem igualmente ao usar um pivô distante da mediana.
Medida da desordem
A medida da desordem a ser escolhida para fins de quicksort é simples.
R: A que distância da mediana está o pivô fixo, comparado aos dados aleatórios?
Se você insistir em usar a partição Lomuto e se considerar que valores duplicados são permitidos, precisará adicionar o seguinte teste contra a aleatoriedade:
B: Quantos elementos duplicados existem, em comparação com o aleatório.
É claro que é bastante tolo supor que valores duplicados são permitidos no seu conjunto de dados e ainda avaliar a partição Lomuto, portanto, você provavelmente deve eliminar duplicatas antecipadamente ou alternar para a partição Hoare ou assumir que as duplicatas são raras.
Ambas as medidas são triviais para quantificar usando estatísticas.
Podemos descartar dados patológicos
Quaisquer outros desvios da aleatoriedade não serão importantes para fins de análise do quicksort. Enquanto o pivô estiver próximo da mediana, ele terá um bom desempenho em todos os dados que não são patológicos.
A distância do aleatório teria que ser realmente grande para ser rapidamente patológica, para que possamos descartar isso.
Nunca use pivôs fixos no código real
Observe que, se você escrever um código real com um pivô fixo *) (seja qual for o pivô), estará se abrindo para um ataque de negação de serviço, porque um invasor pode inserir um valor patológico nesse ponto e, portanto, você deve sempre escolher um elemento aleatório como pivô.
*) ou vários pivôs, se você escolher o melhor de x pivôs.
fonte