Universidade Federal do Paraná
Departamento de Informática
Disciplina CI056 - Algoritmos e Estruturas de Dados II
2o Período do Bacharelado em Ciência da Computação
Também oferecida ao Bacharelado em Matemática Industrial
Prof. Elias Procópio Duarte Jr.

Trabalho Prático 2: Pesquisa e Ordenação

Data de Entrega: 12 de novembro de 2010 (mais de 3 semanas de prazo, não haverá adiamento, organize-se! desconto de 50% da nota por dia de atraso)

OBS.: O trabalho deve ser feito em dupla.

A loja de vídeo-games OrdPesq cadastra seus jogos usando um identificador para cada um dos itens em seu catálogo. Este código consiste de um número inteiro tal que 0 <= código <= 1000. Os códigos dos jogos no estoque estão armazenados em um vetor não ordenado. Você deve escrever um programa que permite a um cliente da loja pesquisar pelo código a disponibilidade de um jogo no estoque.

  1. O vetor de inteiros contendo o estoque da OrdPesq tem sempre 128 posições. Preencha este vetor com números aleatórios entre 0 e 1000. Você deve usar recursos da linguagem C ou Pascal para gerar os números aleatórios. Atenção: confira que o programa não está gerando sempre os mesmos números aleatórios!
  2. Ordene este vetor usando o método da seleção (SelectSort), e o QuickSort. Em outras palavras, você vai ordenar o vetor não ordenado com dois métodos diferentes, um de cada vez. Seu programa deve contar quantas comparações cada método utiliza para ordenar o vetor.
  3. O programa oferece a possibilidade de repetir o experimento 1000 (mil) vezes, isto é, nesta opção são gerados mil vetores de números aleatórios, e faça a ordenação com os dois métodos contando a quantidade de comparações de cada método para cada execução. A saída desta opção é a média aritmética e o desvio padrão do número de comparações de cada método considerando as 1000 (mil) execuções.
  4. Seu programa deve também permitir que um usuário faça uma pesquisa no catálogo da OrdPesq. O usuário entra com o código de um jogo e recebe a informação da sua disponibilidade no estoque (disponível/não-disponível). Implemente tanto a Pesquisa Sequencial (vetor não ordenado) como a Pesquisa Binária (vetor ordenado).
  5. Faça um procedimento que gera uma consulta aleatória, e repita as pesquisas 1000 (mil) vezes (com 1000 (mil) consultas geradas aleatoriamente para cada método). Calcule a média aritmética e o desvio padrão do número de comparações da Pesquisa Binária e da Pesquisa Sequencial.

ENTREGA DO TRABALHO

Deve ser construída uma página Web, que contém em documentos HTML, os seguintes itens:

  • Relatório de como foi feito o trabalho e quais foram os resultados obtidos. Use desenhos, diagramas, figuras, todos os recursos que permitam ao professor compreender como a dupla estruturou o trabalho e quais resultados obteve.
  • Código Fonte comentado. ATENÇÃO: acrescente a todo programa a terminação ".txt" para que possa ser diretamente aberto em um browser. Exemplos: lista.pas.txt ou pilha.c.txt
  • Logs de execução dos processos cliente/servidores, que demonstrem a execução correta destes processos. Os testes devem ser exaustivos até o ponto que demonstrem com clareza a funcionalidade correta do sistema.

    Observações:

  • Não serão aceitos trabalhos impressos, nem em meio ótico/magnético.
  • Alguns trabalhos serão defendidos no laboratório, portanto certifique-se que seu trabalho funciona aqui.

    Importante: capriche na legibilidade e organização.

    Prof. Elias P. Duarte Jr.     Departamento de Informática     UFPR