Fazer a análise do algoritmo misto entre o QuickSort e o algoritmo de ordenação por Seleção, escolhendo o limite ideal para a transição entre os dois algoritmos.
O algoritmos misto que deve ser implementado é o seguinte:
QuickSelect(V,a,b) Se b-a+1 < k Seleção(V,a,b) Devolva V m <-- Particiona(V,a,b,v[b]) QuickSelect(V,a,m-1) QuickSelect(V,m+1,b) Devolva V \end{function}
onde Seleção(V,a,b) é o algoritmo de ordenação por seleção, Particiona(V,a,b,p) é o algoritmo de partição do QuickSort e k é o limite de transição entre os algoritmos.
Os objetivos deste trabalho são a implementação propriamente dita de algoritmos de ordenação e a análise do custo do algoritmo misto para a determinação do melhor valor para o limite k.
A entrada e a saída devem ser feitas pelas entradas e saídas padrão
(stdin
e stdout
). O formato dos dois arquivos será de um inteiro
por linha. Exemplo de entrada e saida: trab1_teste.in e trab1_teste.out.
O trabalho deve ser feito em linguagem C ou C++ de forma que possa ser compilado e executado nas servidoras de computação do Departamento de Informática.
O nome do executável deve ser: ordena
Não deve ter nenhuma opção de linha comando e a forma esperada de execução é descrita abaixo.
Além dos arquivos fonte, deve ser entregue um makefile
e um relatório com
no máximo 2 páginas no formato PDF contendo a análise de qual o valor máximo do limite "k" para a troca de algoritmo (e.g., graficos e explições) e a documentação sintetizada do sistema implementado. Qualquer particularidade deve estar descrita neste texto.
Para compilar será usado o comando make
(sem nenhum parâmetro), portanto preparem o Makefi para fazer isso.
Para testar será executado um script como o abaixo.
$ ./ordena < teste.in > teste.out $ diff teste.sol teste.outOnde
teste.in
é o arquivo de entrada do teste e teste.sol
é o esperado como saída.O trabalho deve ser empacotado em um arquivo login.tar.gz, onde "login" é uma string com o login do aluno nas servidoras do DInf. Ao descompactar este arquivo deverá ser criado um diretório de nome "login" que conterá todos os demais arqus. Caso não possua login utilizar o formato "nome_sobrenome.tar.gz". O make
e o script acima deverão funcionar dentro deste diretório (não em subdiretórios).
Este arquivo deve ser enviado por e-mail ao endereço do professor com o assunto "CI701-trab1 " (exatamente). IMPORTANTE: Minha caixa de email usa o assunto do email como filtro.
O trabalho é individual.