Algoritmos e Estrutura de Dados I - AE22CP - 2013/2

Bruno César Ribas

Exercícios

1. O que é Algoritmo?

Bubble, Selection e Inserção

1. Implemente o Algoritmo Bubble Sort

2. Modifique o seu Algoritmo Bubble Sort e faça ele imprimir quantas operações de troca e quantas comparações foram feitas.

3. Implemente o Algoritmo Selection Sort

4. Modifique o seu Algoritmo Selection Sort e faça ele imprimir quantas operações de troca e quantas comparações foram feitas.

5. Compare o tempo de execução do Bubble e Selection sort para entradas aleatórias até 100000 elementos.

6. Escreva uma versão recursiva do algoritmo de ordenação por seleção

7. Na função selecao, que acontece se trocarmos "for (i = 0" por "for (i = 1"? Que acontece se trocarmos "for (i = 0; i < n-1" por "for (i = 0; i < n" ?

8. Na função "menor", troque a comparação "v[j] < v[min]" por "v[j] <= v[min]". A nova função continua produzindo uma ordenando crescente de v[0..n-1]?

9. Escreva uma função que permute os elementos de um vetor inteiro v[0..n-1] de modo que eles fiquem em ordem decrescente.

10. Escreva uma função que coloque em ordem lexicográfica um vetor de strings. Use o algoritmo de seleção.

11. Resolva a questão 3 da Segunda de prova de 2012-1

12. Suponha que cada elemento de um vetor é um registro com dois campos: um é um inteiro e outro uma string:

         struct registro {int aa; char *bb;};
    

    Escreva uma função que rearranje o vetor de modo que os campos aa fiquem em ordem crescente. Escreva outra função que rearranje o vetor de modo que os campos bb fiquem em ordem lexicográfica.

13. Implemente o Algoritmo de Ordenação por Inserção

14. Escreva uma versão recursiva do algoritmo de ordenação por inserção.

15. Na função insercao, troque a comparação "v[i] > x" por "v[i] >= x". A nova função continua produzindo uma ordenação crescente de v[0..n-1]?

16. Que acontece se trocarmos "for (j = 1" por "for (j = 0" no código da função insercao?

17. Que acontece se trocarmos "v[i+1] = x" por "v[i] = x" no código da função insercao?

18. O papel do for interno na função insercao é encontrar o ponto onde v[j] deve ser inserido em v[0..j-1]. Considere fazer isso com uma busca binária. Analise o resultado.

19. Escreva uma função que permute os elementos de um vetor inteiro v[0..n-1] de modo que eles fiquem em ordem decrescente.

20. Escreva uma função que coloque em ordem lexicográfica um vetor de strings. Use o algoritmo de inserção.

--
Last Modified: Tue Jan 21 18:52:11 2014.