(revisado em Thu Apr 15 12:10:52 2010)

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:

  QuickSortSeleção(V,a,b)
     Se b-a+1 < k
        Seleção(V,a,b)
        Devolva V
     m <-- Particiona(V,a,b,v[b])
     QuickSelectionSort(V,a,m-1)
     QuickSelectionSort(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.

O nome do executável deve ser ordena.

Não devem ter nenhuma opção de linha comando.

O que deve ser entregue:

Além dos arquivos fonte, deve acompanhar um makefile e um relatório com no máximo 2 páginas contendo a análise (possivelmente com gráficos) 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

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.

Forma de entrega:

O trabalho deve ser empacotado em um arquivo login1-login2.tar.gz, onde login1-login2 é uma string com os logins dos integrantes da equipe nas servidoras do DInf. Ao descompactar este arquivo deverá ser criado um diretório de nome login1-login2 que conterá todos os demais arquivos. 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 da sua turma (andre ou eduardo) com o assunto "CI056-trab1" (exatamente).

Equipe:

O trabalho pode ser feito em equipes de 2 (dois) ou 3 (três) alunos.