Análise de algoritmo

Universidade Estadual Do Sudoeste Da Bahia - Uesb

Departamento de Ciências Exatas – DCE
Curso: Ciência da Computação

Disciplina: Análise de Algoritmos

Professora: Aline Silva Costa
ALUNOS: _____________________________________________ Data: _____/_____/____

Atividade de Avaliação – Unidade II - Valor: 3,0

Dada a implementação dos seguintes algoritmos em C++ e Java (escolher uma das duas linguagens) a. Bubblesort b. InsertionSort c. SelectSort d. MergeSort e. QuickSort f. HeapSort

1) Faça testes com vetores em ordem crescente {1,2,3,4…, n-1, n}, “não ordenados” (em ordem decrescente) {n, n-1, n-2, ..., 2, 1}e com elementos aleatórios para calcular tempo médio (Sugestão: usar funções de geração de números aleatórios). Calcular o tempo de ordenação em milisegundos para cada caso, para cada algoritmo, com vetores de tamanhos variados e construir tabelas e gráficos comparativos numa planilha eletrônica.

▪ Comparar algoritmos de mesmo crescimento assintótico e ver a performance relativa. Comparar para vetores de vários tamanhos nos três casos (melhor caso, pior caso e caso médio) (1,0).

1) Uma estratégia muito utilizada no quicksort para evitar o caso em que o pivô é o maior ou o menor elemento da lista (pior caso), consiste no seguinte procedimento: Considera-se três elementos da sublista, o primeiro, o último e o elemento de posição k= (p+u) DIV 2. Comparamos os elementos entre si e alocamos o maior deles no fim da sublista e o segundo maior no início da lista. Implemente essa estratégia no algoritmo quicksort. Faça comparações entre o quicksort sem essa estratégia e com essa estratégia. Dê o tempo T(n) de computação para o pior caso desta estratégia. (1,0) 2) Escrever uma conclusão acerca das análises realizadas (1,0)

Obs: Informar máquina utilizada (processador, memória e