olá, estou com um problema, na faculdade tenho um trabalho para explicar a diferença no desempenho do quicksort por Lomuto e Hoare, mas não estou achando muitas referencias em portugues, e meu ingleês é pessimo, se alguem puder me ajudar e explicar como ambos funcionam e a diferença para que eu possa fazer o trabalho. OBS: o trabalho não é isso, é mais avançado, porem preciso entender para fazer todo o artigo explicado.
1
resposta
resposta
quicksort por Lomuto e Hoare
Opa Jônatas,
Essa página do professor Paulo Feofiloff explica bem o algoritmo (mas creio que só trata da versão de Hoare) https://www.ime.usp.br/~pf/algoritmos/aulas/quick.html
A diferença entre os dois é bastante sutil e complicada e se dá na maneira em que é feita a separação do vetor. A versão de Lomuto melhora o comportamento do algoritmo na média.
A maior parte da literatura está em inglês, mas o livro Introduction to Algorithms de Cormen, Leiserson, Rivest e Stein foi traduzido e explica bem a diferença. Ele é bem comum nas bibliotecas das universidades.