ex 1- QuickSort

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

----- 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