Atps 2 etapa

ETAPA 2

Aula-tema: Análise de desempenho de alguns algoritmos clássicos de busca, ordenação e sobre grafos.

Essa atividade é importante para que você aprenda a analisar algoritmos de ordenação por seleção e por inserção.
Para realizá-la, é importante seguir os passos descritos.

PASSOS

Passo 1 (Equipe)

Cite as vantagens e desvantagens dos algoritmos de ordenação por seleção e de ordenação por inserção. Explicar o funcionamento de cada um deles.

Ordenação por seleção: é um dos métodos mais simples que existem. Além disso, o método possui um comportamento espetacular quanto ao numero de movimentos de registros, cujo tempo de execução é linear no tamanho da entrada, o que é muito difícil de ser batido por qualquer outro método. Consequentemente, este é o algoritmo a ser utilizado para arquivos com registros muito grandes. Em condições normais, com chaves do tamanho de uma palavra, este método é bastante interessante para arquivos pequenos.
Como aspectos negativos cabe registrar que: (I) o fato de o arquivo já estar ordenado não ajuda em nada, pois o custo continua quadrático; (II) o algoritmo não é estável, pois ele nem sempre deixa os registros com chaves iguais na mesma posição relativa.
O principio de funcionamento é o seguinte: selecione o menor item do vetor e a seguir troque-o com o item que está na primeira posição do vetor. Repita essas duas operações com os n-1 itens restantes, depois com os n-2 itens, até que reste apenas um elemento.

Ordenação por inserção: o método da inserção é o método a ser utilizado quando o arquivo está “quase” ordenado. É também um bom método quando se deseja adicionar uns poucos itens a um arquivo já ordenado e depois obter outro arquivo ordenado: neste caso, o custo é linear. O algoritmo de ordenação por inserção e quase tão simples quanto o algoritmo de ordenação por seleção. Além disso, o método de ordenação por inserção é estável, pois ele deixa os registros com chaves iguais na mesma posição relativa.
Este é o