RE: Arlgoritmo Particione

[Paulo Feofiloff <pf@ime.usp.br>]

Danilo Eiji Seki writes:

 > Sobre o algoritmo Particione que esta na pagina (eu nao pude ir
 > aa ultima aula de MAC122), nao seria melhor fazer
 > 
 >   do ++i while (a[i] <= v);
 >   do --j while (v <= a[j] && l < j);
 > 
 > ao inves do que esta la? (sem os "=")

Dá vontade de fazer isso, não dá?
Mas se você fizer isso, o índice i pode passar de r
(o que seria um desastre).
Poderíamos acrescentar uma comparação de i com r,
mas o resultado seria um pouco pior do ponto de vista prático.
O livro discute isso na página 308.

 > Como se exige da funcao que os elementos da esqueda sejam
 > menores *ou iguais* e os da direita maiores *ou iguais*,
 > essa modificacao nao evitaria que fossem realizados trocas
 > por causa de elementos iguais?
 > 
 > Pelo que eu vi la, um padrao 6666666 sofreria varias trocas,
 > mas apos a modificacao sofreria apenas uma.

PF