Universidade Tecnológica Federal do Paraná (UTFPR)
Departamento Acadêmico de Informática (DAINF)
Computação II
Professor: Alex Kutzke ([email protected])
Especificação do Segundo Trabalho Prático
Análise de Algoritmos de Ordenação
1
Sumário e Objetivo
O trabalho aqui especificado visa a implementação de seis algoritmos de
ordenação e a produção de uma análise crı́tica com relação ao desempenho
destes.
O trabalho deve ser implementado inteiramente em Linguagem C.
Um relatório no formato PDF deve ser enviado juntamente ao(s) código(s)
fonte do programa.
A entrega deve ser realizada pelo site da disciplina até a seguinte data:
06/12/2015 às 23:59h.
O trabalho deve ser realizado em grupos de até 3 alunos.
As próximas Seções descrevem a especificação do trabalho em detalhes.
1
2
Detalhes de implementação
O objetivo deste trabalho é implementar e comparar o desempenho dos
seguintes algoritmos de ordenação:
• Bubble-sort;
• Selection-sort;
• Insertion-sort;
• Merge-sort;
• Heap-sort;
• Quick-sort.
Para tanto, cada grupo deve implementar um programa em linguagem C
capaz de executar os algoritmos acima para um conjunto de N números inteiros. Dois tipos de entrada são possı́veis: por teclado e geração automática
de números.
2.1
Parâmetros na linha de comando
O programa implementado pode receber três parâmetros pela linha de
comando (um obrigatório e dois opcionais):
$ sorting <alg> [input] [print]
O primeiro parâmetro, alg, é obrigatório e indica qual algoritmo deve ser
utilizado para a ordenação dos dados de entrada. Os valores possı́veis para
esse parâmetro são:
2
bs : Bubble-sort;
ss : Selection-sort;
is : Insertion-sort;
ms : Merge-sort;
hs : Heap-sort;
qs : Quick-sort;
O segundo parâmetro é opcional e indica se os números a serem ordenados
devem ser gerados de maneira automática. Na ausência desse parâmetro, o
programa deverá ler os números a partir do teclado. Os valores possı́veis
para esse parâmetro são:
order : gera automaticamente conjuntos de elementos em ordem crescente;
reverse : gera automaticamente conjuntos de elementos em ordem decrescente;
random : gera automaticamente conjuntos de elementos aleatórios.
O último parâmetro, também opcional, indica se o programa deve exibir
os elementos ordenados. O único valor possı́vel para esse parâmetro é a
palavra “print”. Alguns exemplos de execução:
$ sorting bs print
$ sorting hs
$ sorting qs random print
# ordena e imprime N números lidos do teclado
com o algoritmo bubble-sort
# ordena N números lidos do teclado com o
algoritmo heap-sort
# ordena e imprime números aleatórios com o
3
$ sorting is order
2.2
algoritmo quick-sort
# ordena um conjunto de números já em ordem
crescente com o algoritmo insertion-sort
Entrada e saı́da
Como descrito anteriormente, o programa a ser implementado terá duas
opções de entrada: teclado ou números gerados automaticamente. Cada tipo
de entrada irá produzir um comportamento de saı́da diferente.
Para o primeiro tipo, leitura através do teclado, o programa deverá ler um
número inteiro (do tipo long) N , que representará a quantidade de elementos
que se deseja ordenar. Na sequência, o programa deverá ler N números
inteiros (também do tipo long).
A saı́da para este caso será a seguinte:
[Lista dos números ordenados apenas se o par^
ametro print foi passado]
N
Número de trocas
Número de comparaç~
oes
Tempo
Ou seja, se o parâmetro print foi passado, deve-se exibir a lista dos
números ordenados em ordem crescente. Na sequência, devem ser expostos
os seguintes dados: número de elementos ordenados, quantidade de trocas e
comparações executados pelo algoritmo de ordenação e, por fim, o tempo em
milisegundos que o algoritmo levou para ordenar o conjunto de elementos.
Por exemplo:
$ sorting ss print
5
5 4 3 2 1
1 2 3 4 5
# entrada
# entrada
# saı́da
4
5
4
10
$ sorting ss
5
5 4 3 2 1
5
4
10
XYZ
# saı́da
XYZ
# entrada
# entrada
# saı́da
O comportamento do programa quando o parâmetro para geração automática é passado pela linha de comando deve ser diferente. Nesse caso,
o programa deve realizar uma sequencia de ordenações para um conjunto
determinado de tamanhos de entrada. Esse conjunto é o seguinte: N ∈ {10,
20, 30, 40, 50, 60, 70, 80, 90, 100, 200, 300, 400, 500, 600, 700, 800, 900,
1000, 1500, 2000, 2500, 3000, 3500, 4000, 4500, 5000, 5500, 6000, 6500, 7000,
7500, 8000, 8500, 9000, 9500, 10000, 100000, 1000000, 10000000}.
Em outras palavras, o programa deverá gerar e ordenar 40 conjuntos
diferentes de elementos (um de cada vez, iniciando pelo menor valor de N ),
seguindo as regras definidas pelo parâmetro passado, e exibir a saı́da para
cada um dos casos. Por exemplo:
$ sorting ss order
10
N_COMPS
N_TROCAS
TEMPO
20
N_COMPS
N_TROCAS
TEMPO
30
N_COMPS
N_TROCAS
TEMPO
...
10000000
N_COMPS
N_TROCAS
2.3
TEMPO
Implementação dos algoritmos de ordenação
Cada um dos algoritmos deve ser implementado como uma função em
linguagem C, seguindo o seguinte protótipo:
5
void nome_alg_ord(long * v, long n, long * comps, long * trocas)
O número de trocas e de comparações executadas pelo algoritmo deve ser
retornado ao programa através dos parâmetros comps e trocas, passados por
referência.
3
Relatório
Além do código-fonte do programa implementado, cada grupo produzirá
um relatório comparando o desempenho dos algoritmos.
Este relatório deve conter uma análise crı́tica, a qual apresenta e justifica
o melhor e o pior caso de cada algoritmo, bem como, a descrição de suas
complexidades.
O relatório deve, também, conter gráficos que relacionem o número de elementos (e sua forma: ordenado crescentemente, ordenado decrescentemente
ou aleatório) e o desempenho de cada algoritmo (comparações, trocas e/ou
tempo). Por exemplo, a Figura 1 apresenta a comparação do tempo de processamento utilizado pelos algoritmos bubble-sort, selection-sort e insertionsort para diferentes tamanhos de entrada.
4
Entrega
O trabalho deve ser entregue através do site da disciplina:
http://http://alex.kutzke.com.br/courses/4
Na opção “Atividades”, encontre a atividade “Trabalho 2” e preencha o
formulário para a submissão do trabalho.
6
600
Bubble
Selection
Insertion
500
400
300
200
100
0
0
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000
Figura 1: Tempo de processamento utilizado pelos algoritmos bubble-sort,
selection-sort e insertion-sort para diferentes tamanhos de entrada.
Cada grupo pode realizar quantas submissões forem necessárias, pois apenas a mais recente será considerada.
Qualquer dúvida entre em contato através do email: [email protected].
utfpr.edu.br
7