AED II - Ordenação

  • Published on
    10-Apr-2016

  • View
    218

  • Download
    2

Embed Size (px)

DESCRIPTION

Exercicios sobre algoritmos de ordenao, quicksort, merge sort, heap sorte entre outros.

Transcript

<ul><li><p>Pontifcia Universidade Catolica de Minas GeraisCurso de Cie^ncia da Computac~aoDisciplina: Algoritmos e Estruturas de Dados II</p><p>Trabalho Pratico IV - Pesquisa e Ordenac~ao</p><p>1 Regras Basicas</p><p>1. extends TP3RegrasBasicas;</p><p>2. Nos exerccios de ordenac~ao ou estruturas de dados, se dois objetos tiverem a mesma chave de</p><p>pesquisa, eles ser~ao ordenados pela data da partida e, em seguida, pela ordem alfabetica do</p><p>mandante.</p><p>2 Descric~ao</p><p>1. Pesquisa Sequencial: Faca a inserc~ao de alguns objetos no nal de uma Lista e, em seguida,</p><p>faca algumas pesquisas sequenciais. A chave primaria de pesquisa sera a probabilidade de vitoria</p><p>do mandante. A entrada padr~ao e composta por duas partes onde a primeira e igual a entrada</p><p>da primeira quest~ao do Trabalho Pratico III. As demais linhas correspondem a segunda parte.</p><p>A segunda parte e composta por varias linhas. Cada uma possui um elemento que deve ser</p><p>pesquisado na Lista. A ultima linha tera a palavra FIM. A sada padr~ao sera composta por</p><p>varias linhas contendo as palavras SIM/NAO (sem acento) para indicar se existe cada um dos</p><p>elementos pesquisados. Alem disso, crie um arquivo de log na pasta corrente com o nome</p><p>matrcula sequencial.txt com uma unica linha contendo sua matrcula, tempo de execuc~ao do</p><p>seu algoritmo e numero de comparac~oes. Todas as informac~oes do arquivo de log devem ser</p><p>separadas por uma tabulac~ao 'nt'.</p><p>2. Pesquisa Binaria: Repita a quest~ao anterior, contudo, usando a Pesquisa Binaria. A en-</p><p>trada e a sada padr~ao ser~ao iguais as da quest~ao anterior e o nome do arquivo de log seja</p><p>matrcula binaria.txt.</p><p>3. Ordenac~ao por Selec~ao: Na classe Lista, implemente o algoritmo de ordenac~ao por selec~ao</p><p>considerando que a chave de pesquisa e o atributo mandante. A entrada e a sada padr~ao</p><p>s~ao iguais as da primeira quest~ao do Trabalho Pratico III, contudo, a sada corresponde</p><p>aos objetos ordenados. Alem disso, crie um arquivo de log na pasta corrente com o nome</p></li><li><p>matrcula selecao.txt com uma unica linha contendo sua matrcula, numero de comparac~oes</p><p>(entre elementos do array), numero de movimentac~oes (entre elementos do array) e o tempo de</p><p>execuc~ao do algoritmo de ordenac~ao. Todas as informac~oes do arquivo de log deve ser separadas</p><p>por uma tabulac~ao 'nt'.</p><p>4. Ordenac~ao por Selec~ao Recursiva: Repita a quest~ao anterior, contudo, usando a Selec~ao</p><p>Recursiva. A entrada e a sada padr~ao ser~ao iguais as da quest~ao anterior e o nome do arquivo</p><p>de log seja matrcula selecaoRecursiva.txt.</p><p>5. Ordenac~ao por Inserc~ao: Repita a quest~ao de Ordenac~ao por Selec~ao, contudo, usando o</p><p>algoritmo de Inserc~ao, fazendo com que a chave de pesquisa seja o atributo visitante e o nome</p><p>do arquivo de log seja matrcula insercao.txt.</p><p>6. Shellsort: Repita a quest~ao de Ordenac~ao por Selec~ao, contudo, usando o algoritmo Shellsort,</p><p>fazendo com que a chave de pesquisa seja o atributo probabilidade de vitoria do mandante</p><p>e o nome do arquivo de log seja matrcula shellsort.txt.</p><p>7. Heapsort: Repita a quest~ao de Ordenac~ao por Selec~ao, contudo, usando o algoritmo Mergesort,</p><p>fazendo com que a chave de pesquisa seja o atributo probabilidade de empate e o nome do</p><p>arquivo de log seja matrcula heapsort.txt.</p><p>8. Quicksort: Repita a quest~ao de Ordenac~ao por Selec~ao, contudo, usando o algoritmo Quicksort,</p><p>fazendo com que a chave de pesquisa seja o atributo probabilidade de vitoria do visitante</p><p>e o nome do arquivo de log seja matrcula quicksort.txt.</p><p>9. Counting Sort: Repita a quest~ao de Ordenac~ao por Selec~ao, contudo, usando o algoritmo</p><p>Mergesort, fazendo com que a chave de pesquisa seja o atributo numero de gols do mandante</p><p>e o nome do arquivo de log seja matrcula countingsort.txt.</p><p>10. Bolha: Repita a quest~ao de Ordenac~ao por Selec~ao, contudo, usando o algoritmo da Bolha,</p><p>fazendo com que a chave de pesquisa seja o atributo numero de gols do visitante e o nome</p><p>do arquivo de log seja matrcula bolha.txt.</p><p>11. Mergesort: Repita a quest~ao de Ordenac~ao por Selec~ao, contudo, usando o algoritmo Merge-</p><p>sort, fazendo com que a chave de pesquisa seja o atributo numero de gols na partida e o</p><p>nome do arquivo de log seja matrcula mergesort.txt.</p></li></ul>