Questão 4 da prova do semestre passado

[xth1]

Qual o maior número de vezes que o maior elemento da entrada pode ser movido
durante a execução do Quicksort?

Alguém chegou a uma conclusão sobre essa questão?

[maycon sambinelli]

Então, eu respondi assim:

O maior nº de vezes que o maior elemento x pode ser movido é n - 1
vezes. Isso acontece quando o elemento x está na primeira posição,
como o lugar correto para x é a última posição, de alguma forma o
quick-sort terá que desloca-lo para lá. Como nenhum elemento do vetor
é maior que x, então ele só se desloca para a direita. Então o pior
caso é qndo ele se desloca apenas uma unidade por vez para a direita,
o que gastará n - 1 movimentos. Para ver que é possível se deslocar
apenas 1 movimento para a esquerda, basta pegar uma entrada onde o
maior elemento está na primeira posição e o pivo é o segundo maior
elemento.

// essa prova ta mais difícil que a lista... =/

[]'s

--
Maycon Sambinelli (@msambinelli)
Mestrando em Ciência da Computação
Universidade Estadual de Campinas (UNICAMP)

Bacharel em Ciência da Computação
Universidade Estadual de Maringá (UEM)

:wq

[Thiago S. A.]

Acho que deve ser n-1 mesmo, pelo que eu verifiquei é impossível ter mais do que isso.