MAC 122 Princípios de Desenvolvimento de Algoritmos

		Segunda lista de exercícios (turma do básico)

	      Entregar na aula de 14set99. Prazo improrrogável.

			   Equipes de <= 2 alunos.

1. (6.26) Qual dos três métodos de ordenação elementar, entre ordenação por
   seleção, por inserção e o método da bolha, é mais rápido para arquivos
   cujas chaves são todas idênticas? Justifique.

2. Um método de ordenação é estável se ele preserva a ordem relativa de ítens
   com chaves idênticas. (Veja na página 259 do livro)

   2a. (6.14) Ordenação por seleção é estável? Justifique.

   2b. (6.18) Ordenação por inserção é estável? Justifique.

   2b. (6.22) O método da bolha é estável? Justifique.

3. Implemente uma versão do método da bolha que alterna o sentido de percurso
   do vetor entre passes esquerda-a-direita e direita-a-esquerda. Este método,
   mais rápido mas mais difícil de ser implementado, chama-se de "shaker
   sort". Para maiores informações, veja a Figura 6.7.

   Teste o seu programa num computador, usando o driver de algoritmos de
   ordenação visto em aula.

---

MAC 122 Princípios de Desenvolvimento de Algoritmos

---

e-mail: Imre Simon <is@ime.usp.br>

Last modified: Thu Aug 26 19:22:14 EST 1999