Análise do algoritmo quicksort §

---

Suponha que o quicksort rode sobre um vetor v que está ordenado em ordem decrescente, conforme abaixo.

Suponha que o partition sempre escolhe o primeiro elemento como pivô.

1. Simule o quicksort. §

2. Dê a formula aberta deste caso, com base na sua simulação. §

Se

Generalizando:

E vai parar quando ou

3. Calcule o tempo de execução com base neste fórmula aberta. §

Nessa situação o algoritmo encontra-se no pior cenário do quicksort .

---

Suponha que você use o quicksort para ordenar um vetor muito grande e que você tenha um algoritmo que efetivamente uma permutação no vetor em . Suponha também que você cronometre a ordenação e que você note que já passou tempo suficiente para o quicksort ordenar em .

1. Vale a pena parar a ordenação, permutar o vetor e começar tudo de novo? §

A permutação do vetor pode ser uma boa alternativa, pois estatísticamente a chance de permutar os elementos e cair no pior caso também. Em geral, cairá no caso médio o qual o tempo de execução será muito menor.

---

Ordenar muitos documentos cuja chave é um natural menor que 1000 em tempo para o pior caso e localmente ( para memória). Escreva este algoritmo, sem programar.

Referências §

---