CCM0128 - Computação II (2025i)

Considere a versão do quicksort implementada no programa QuickKR.java abaixo. Nessa versão do quicksort, o algoritmo de partição usado é o algoritmo que aparece no livro de Kernighan & Ritchie. Uma versão equivalente a essa partição é dada no livro de Cormen, Leiserson, Rivest & Stein.

Considere uma chamada de sort() de QuickKR.java com um array \(a\) com \(N\) entradas como parâmetro. Ademais, suponha que um certo valor $x$ ocorre $m$ vezes no array $a$. Neste exercício, você deve provar que sort() fará pelo menos $m\choose2$ chamadas de less(). Assim, se $m$ for linear em $N$, essa chamada de sort() custará tempo quadrático em $N$. A conclusão é que o algoritmo de partição de K&R e CLRS é ruim para entradas que tem um elemento repetido muitas vezes, e portanto não deve ser usado.

Seja $C(a)$ o número total de chamadas de less() que sort() faz com entrada $a$. Para naturais $m$ e $N$ com $m\leq N$, seja

\(
f(m,N)=\min\{C(a):a\text{ tem $N$ elementos e algum $x$ ocorre $m$ vezes em $a$}\}.
\)

(1) Prove que $f(m,m)={m\choose2}$ para todo $m\geq0$.

(2) Suponha agora que $m<N$. Seja $a$ um array com $N$ entradas e suponha que exista um valor $x$ que ocorre $m$ vezes em $a$. Prove que $C(a)$ ou é pelo menos $f(m,N')$ para algum $N'<N$ ou é pelo menos $f(m-1,N')+m-1$ para algum $N'<N$.

(3) Deduza de (1) e (2) que $f(m,N)\geq{m\choose2}$ para quaisquer naturais $m$ e $N$ com $m\leq N$. [Sugestão. Faça indução em $N$.]