Primeiro Trabalho Prático

CI701 - 2016/2
Prof. Eduardo Almeida

Ordenação

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.

Algoritmo misto:

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.

Objetivos:

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.

Entrada e Saída:

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.

Requisitos mínimos:

O trabalho deve ser feito de forma que possa ser compilado e executado nas servidoras de computação do Departamento de Informática. Atualmente as servidoras possuem a seguinte lista de software: Linux version 4.6.4-terms+ (root@urquell) (gcc version 5.3.1 20160413 (Ubuntu 5.3.1-14ubuntu2.1) ), java version "1.8.0_91", Python 2.7.11+, ruby 2.3.1p112 (2016-04-26) [x86_64-linux-gnu]

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.

O que deve ser entregue:

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 Makefile para fazer isso mesmo que o programa seja implementado em linguagens interpretadas (e.g., Java, Python, Ruby).

Para testar será executado um script como o abaixo.

$ ./ordena < teste.in > teste.out
$ diff teste.sol teste.out

Onde teste.in é o arquivo de entrada do teste e teste.sol é o esperado como saída.
Caso o teste seja positivo (não imprime nada) será analisado o código fonte e o relatório.
Os fontes também devem ser comentados para uma possível análise (e.g., Javadoc).

Forma de entrega:

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.

Equipe:

O trabalho é individual.