Re: Re:ex 1- QuickSort

["Daniel Vieira" <dvieira@ime.usp.br>]

Gustavo,

Eu acho que não vou ter tempo ainda hoje para digitar a demostração.
Entretanto, eu vou assistir a aula e a monitoria de AA hoje, portanto é só
você me procurar, que eu te mostro.
at+

Daniel

----- Original Message -----
From: "gustavo_bi" <gustavo_bi@bol.com.br>
To: <dvieira@ime.usp.br>
Sent: Sunday, October 29, 2000 4:34 PM
Subject: Re:ex 1- QuickSort


Caro Daniel,
concordo com sua opinião.
Se possível, gostaria de receber a sua demonstração.

Obrigado,
Gustavo.

>
> ----- Original Message -----
> From: "Imre Simon" <is@ime.usp.br>
> To: "Marcelo Amaral Rezende" <trezende@ime.usp.br>
> Cc: <is-5711-00@ime.usp.br>
> Sent: Sunday, October 29, 2000 12:29 PM
> Subject: Re: exercicios
> > De fato, acho que o número correto deveria ser 2^{n-
1} em vez de
> > 2^n. Mas {3^(n-2)}*2 me parece muito grande.
Produzam as 6 permutações
> > de 3 elementos que são candidatas ao pior desempenho
e executem o QS
> > neles, calculando a somatória dos tamanhos dos
trechos que são
> > particionados.
> >
> > Imre Simon
>
> Realmente, parece que o número de permutações é 2^(n-
1). Você deve estar
> pensando que a cada chamada do partition existem dois
casos que ocasionam o
> pior caso. Quando o partition retorna j=1 e quando
retorna j=n-1. Para
> retornar j=1 o pivô do partition deve ser o menor
elemento do vetor, e para
> retornar j=n-1 o pivô deve ser o maior elemento do
vetor. Assim, para cada
> chamada do partiton, apenas dois números podem estar
na primeira posição
> (pivô), resultanto na fórmula
>
> 2    x    2    x    2    x....x    2    x    1    =
2^(n-1)
>
> Entretanto, se você analisar com cuidado o partition,
você percebe que o
> algoritmo retorna j=1, quando o menor  ou o segundo
menor elemento do vetor
> estiver na primeira posição. Faça um teste para o
seguinte vetor
>
>  2 1 3 4 5            (pior caso)
>
>
>
> Bem, pensando que o pivô tem  três possibilidades,
temos um total de
>
>  3          x            3            x
3            ....
> x            2            x            1            =
{3^(n-2)}*2
>
>  Eu sei que eu não estou provando nada, só estou
mostrando a intuição do
> problema. Para concluir esta formula você tem que
tomar cuidado com casos
> desse tipo:
>
>  2 4 1 3 5            (a segunda chamada do partition
não dá no pior caso).
>
>  Mas, é possível mostrar por indução que existem
exatamente {3^(n-2)}*2
> permutações do pior caso. O passo da indução é
delicado, pois o partition
> pode trocar elementos.
>
> Se alguém quiser, eu posso digitar e enviar a
demonstração por e-mail.
>
>  Acho que o Marcelo está de acordo com tudo o que eu
estou falando. Nós
> resolvemos o problema considerando um vetor A de n
elementos distintos.
> Provamos por indução que existem {3^(n-2)}*2
permutações do vetor A que
> fazem o QuickSort visto em aula apresentar a sua pior
performance.
>
>  Se não houver a restrição de elementos distintos para
o vetor de entrada,
> temos n^n permutações possíveis, e muito mais  {3^(n-
2)}*2 permutações do
> vetor que fazem o QuickSort apresentar a sua pior
performance.
>
>  Gostaria de saber se nós entendemos o enunciado
corretamente, ou estamos
> dando a solução para o problema errado.
>
>  Daniel Vieira
>
>
>
>
>


__________________________________________________________________________
Todo brasileiro tem direito a um e-mail grátis
http://www.bol.com.br