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. Exemplo de entrada e saida: trab1_teste.in e trab1_teste.out.

Requisitos mínimos:

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.

O que deve ser entregue:

Os arquivos fonte para serem compilados no executável ordena (ou seja, não é necessario enviar o executavel, pois ele sera compilado), um arquivo makefile para realizar a compilação 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.

Para testar será executado um script como o abaixo.

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

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.