Estrutura de Dados - ARA 7125
Segundo Exercı́cio-Programa - Entrega: 06 de Dezembro de 2014
Tempo de alguns algoritmos de ordenação
Este Exercı́cio-Programa (EP) consiste na implementação dos algoritmos de ordenação Inserç~
ao,
Seleç~
ao, Mergesort, Heapsort e Quicksort. Calcule o espaço gasto por cada algoritmo. Use
a função sizeof para calcular o espaço gasto (em bytes) pelas variáveis.
Para cada algoritmo, calcule também o tempo médio gasto para ordenar vetores com tamanhos 100, 200, 400, 800, 1600, 32000, 64000, 128000, 256000, 512000, 1024000, 2048000,
4096000. O tempo médio deve ser calculado executando cada algoritmo para 50 entradas de um
determinado tamanho. O tempo médio deve ter 7 casas decimais (exatamente).
Para calcular o tempo de um algoritmo, você pode usar, por exemplo:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main(){
clock t start, end;
double cpu time used;
start = clock();
/* Chame um algoritmo aqui. */
end = clock();
cpu time used = ((double) (end - start)) / CLOCKS PER SEC;
return 0;
}
A variável cpu time used armazena o tempo em segundos do algoritmo analisado.
Gerando as entradas para este exercı́cio
Uma entrada pode ser gerada pelo programa em C cria-vetor.c (disponı́vel na página da
disciplina). Compile este programa, dê ao arquivo compilado o nome a.out, e execute este
programa com o parâmetro 100 para gerar uma sequência aleatória com 100 números de inteiros
entre 0 e 9999.
O script gera.sh (somente para o sistema operacional Linux e também disponı́vel na página
da disciplina), gera automaticamente todas as entradas do programa.
Faça um relatório comentando os resultados obtidos. Este relatório deve conter pelo menos
uma tabela mostrando o consumo médio de tempo e o consumo de espaço para cada algoritmo.
Observações importantes:
1. Podem formar grupos com até 3 pessoas.
2. O seu programa deve ser feito em linguagem C. O compilador deve ser o gcc.
3. Você deve implementar os algoritmos vistos em sala de aula.
4. Exercı́cios-Programas atrasados não serão aceitos.
5. Programas com erros de sintaxe (ou seja, existem erros durante a compilação do programa),
receberão nota ZERO. Programas com warning na compilação terão diminuição na nota.
6. Utilize apenas os recursos que foram vistos em aula.
1
7. É importante que seu programa esteja escrito (digitado) de maneira a destacar a estrutura
do programa (boa formatação).
8. O seu programa deve começar com um cabeçalho (linhas em comentários) contendo pelo
menos o seu nome, sua matrı́cula e seu curso.
9. Coloque comentários em pontos convenientes do programa.
10. A entrega do Exercı́cio-Programa deverá ser feita no MOODLE.
11. O Exercı́cio-Programa é individual por grupo. Não copie o programa de outro grupo, não
empreste o seu programa para outro grupo, e tome cuidado para que não copiem seu programa
sem a sua permissão. Todos os programas envolvidos em cópia terão nota ZERO.
2