aeds

Algoritmos e Estrutura de Dados II

Trabalho Prático 1

Aluno: Guilherme Henrique dos Santos Amaral
Turma: A2
Matrícula: 2011027190

(1) Descreva o funcionamento de cada algoritmo.

- Bubblesort: O algoritmo pega um vetor de n elementos desordenado e ordena, por exemplo, em ordem crescente. Para isto ele considera inicialmente todos os n elementos do vetor, e vai comparando de dois em dois a partir do primeiro elemento, no caso iniciando a comparação com o primeiro e o segundo elementos, e caso o primeiro elemento seja maior que o segundo ele os troca de posição, e assim segue com as comparações, depois fazendo do segundo com o terceiro elemento, até chegar à comparação do penúltimo com o último. Após esta última comparação o algoritmo fixa este último elemento do vetor, pois ele já está ordenado, e repete o procedimento considerando n-1 elementos no vetor.
Todo este procedimento é repetido até restar apenas um elemento, onde ele já está ordenado por si só. Segue abaixo um exemplo de ordenação de um vetor de três posições.

Ex.: v={4,2,1} 4 2 1 2 4 1 2 1 4 O último elemento é fixado e não sofre mais alterações 2 1 4 1 2 4 O vetor foi ordenado.

- SelectionSort: O algoritmo pega um vetor de n elementos desordenado e ordena, por exemplo, em ordem crescente. Para isto ele considera inicialmente todos os n elementos do vetor, faz uma busca comparando um a um para encontrar o menor elemento e ao fim dessa busca troca o elemento na posição zero do vetor com o menor elemento q está numa posição aleatória, após isto fixa o primeiro elemento, pois ele já está ordenado e repete o procedimento com os elementos restantes, jogando o menor elemento dentre eles na posição número um, e repete este procedimento até o vetor só ter um elemento, onde um elemento já está ordenado por si só. Segue abaixo um exemplo de ordenação de um vetor