Lista de exercicio 6 - Cormen 2º Edição

Prévia do material em texto

Aluno: Vinicius Barcelos Silva  
Matricula: 108251 
 
7.1­2 
Quando todos os elementos em A são os mesmos, note que a comparação na linha 4 do partição é 
sempre saciada e, portanto, i é incrementado a cada iteração. Desde inicialmente i <­ p ­ 1 e i + 1  
é devolvido o valor retornado é r ­ 1.  
Para fazer o retorno DIVISÓRIA (p + r) = 2, quando todos os elementos são os mesmos, basta modificar o 
algoritmo para verificar se há este caso de forma explícita. 
 
7.1­4 
Para tornar a classificação do QUICKSORT em ordem não­crescente, substituiria a comparação da linha 4 
do PARTITION de “<=” para “>=”. 
“do if A[j] <= x”, para “do if A[j] >= x”.  
 
7.3­1 
Podemos estar interessados ​​no desempenho de pior caso, mas, nesse caso, a aleatoriedade é irrelevante: 
ele não vai melhorar o pior caso. O que randomização pode fazer é fazer a chance de encontrar um cenário 
de pior caso pequeno.