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

Bruno César Ribas

Exercícios

1. O que é Algoritmo?

2. Implemente o Algoritmo Bubble Sort

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

4. Implemente o Algoritmo Selection Sort

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

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

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

8. 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" ?

9. 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]?

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

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

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

13. 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.

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

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

16. 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]?

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

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

19. 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.

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

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

--
Last Modified: Mon Jul 8 18:10:08 2013.