Universidade Federal de Ouro Preto (UFOP)
Departamento de Computação (DECOM – ICEB)
Disciplina: BCC202 - Estruturas de Dados I
Professores: Túlio Toffolo (www.toffolo.com.br)
Reinaldo Fortes ([email protected])
Aula Prática 15-16
Ordenação
Questão 01
Entregar esta questão até o final do dia (até as 23h55).
Implemente o algoritmo MergeSort para ordenar um conjuntos de números.
A entrada será dada por vários casos de teste. Cada caso de teste ocupa uma linha da entrada, e
é composta por um inteiro N indicando o tamanho do vetor a ser ordenado seguido pelos N
inteiros que compõem o vetor. A entrada é finalizada quando N = 0.
A saída de cada caso de teste ocupa uma linha, e é composta pelo vetor ordenado.
Exemplo de entrada:
10 1 2 3 4 5 6 7 8 9 10
9 9 8 3 28 3 5 929 -99 0
0
Exemplo de saída:
1 2 3 4 5 6 7 8 9 10
-99 0 3 3 5 8 9 28 929
Questão 02
Entregar esta questão até o final do dia (23h55).
Implemente o algoritmo QuickSort, escolhendo como pivô o elemento central do vetor, seguindo
o mesmo padrão de entrada e saída definido na questão 01.
Questão 03
Entregar esta questão até o final do dia (23h55).
Implemente o algoritmo QuickSort seguindo o mesmo padrão definido na questão 02, mas
acrescentando a seguinte melhoria: para vetores com poucos elementos (menor ou igual a 10, por
exemplo), utilize o método de ordenação InsertionSort, implementado na prática anterior.
Entrega no Moodle para as questões 1 a 3:
Verifique se seu programa compila e executa na linha de comando antes de efetuar a entrega.
Quando o resultado for correto, entregue um arquivo .ZIP com seu nome, sobrenome e o número
da questão (exemplo: tulio-toffolo-01.zip). O .ZIP deve conter as TADs e o programa principal
(main.c).
BCC202 – Prática 15-16
Data: 24/07/2013
Página 1 de 2
Questão 04
Entregar esta questão até SEXTA-FEIRA (23h55).
Crie quatro arquivos de entrada contendo 4 casos de teste cada um. O valor de N para todos os
casos de teste do primeiro arquivo deverá ser 100, para o segundo 200, para o terceiro 400 e para
o quarto 600. Para cada arquivo, os seguintes casos de teste deverão ser criados: (C1) Sequência
de números aleatórios; (C2) Sequência de números em ordem crescente; (C3) Sequência de
números em ordem decrescente; (C4) Sequência de números iguais.
Execute os casos de teste para os algoritmos das questões 2 e 3, coletando os tempos de
execução da ordenação e analise os resultados. A seguinte tabela deverá ser preenchida para
sua análise, contendo a diferença entre os tempos coletados para o algoritmo da questão 3 e o
algoritmo da questão 2 em cada teste:
Tempo_do_Algoritmo_Q3 – Tempo_do_Algoritmo_Q2
N = 100
N = 200
N = 400
N = 600
C1: Aleatórios
C2: Crescentes
C3: Decrescentes
C4: Iguais
Exemplo de como coletar o tempo de execução da ordenação:
#include <time.h>
:
clock_t tFim, tIni = clock(); // instrução exatamente anterior à chamada
Ordena(); // chamada da função de ordenação
tFim = clock(); // instrução exatamente posterior à chamada
TempoMiliSegundos = (double)(tFim - tIni) * 1000 / CLOCKS_PER_SEC;
Exemplo de como gerar um arquivo de caso de teste (para gerar o arquivo direcione a saída):
#include <stdlio.h>
#include <stdlib.h>
#include <time.h>
int main() {
int I, N = 100; // N pode ser parametrizado em ‘args’
srand(time(NULL)); // Inicia semente para o rand
printf("%d ", N); // primeira linha, C1 – aleatório (entre 0 e 1000)
for(int i=0 ; i < N ; i++) printf("%d ", rand()%1000);
printf("\n%d ", N); // segunda linha, C2 – crescente
for(int i=0 ; i < N ; i++) printf("%d ", i);
printf("\n%d ", N); // terceira linha, C3 – decrescente
for(int i=N ; i < 0 ; i--) printf("%d ", i);
printf("\n%d ", N); // quarta linha, C4 – números iguais
for(int i=0 ; i < N ; i++) printf("%d ", N);
printf("\n0"); // encerramento dos casos de teste
return 0;
}
Entrega no Moodle para a questão 4:
Arquivo .ZIP com seu nome, sobrenome e o número da questão (exemplo: tulio-toffolo-04.zip). O
.ZIP deve conter os arquivos de casos de testes gerados e um arquivo .PDF com seu nome,
sobrenome e o número da questão (exemplo: tulio-toffolo-04.pdf). O .PDF deve conter a
identificação do aluno, a descrição da máquina em que os testes foram realizados (processador,
memória principal, memória cache, etc.), a tabela de tempos de execução coletados, suas
análises e conclusões.
BCC202 – Prática 15-16
Data: 24/07/2013
Página 2 de 2