Classificação (Ordenação) de dados
Exercícios
1. Modifique o código do método de ordenação por bolha para que
ele transforme-se no método de “ordenação por pedra”, ou seja, o
elemento desce ao invés de subir no vetor ordenado.
2. Escreva uma versão recursiva do algoritmo de ordenação por
inserção.
3. No caso do quicksort, considere que o pivô é o elemento central e
apresente a ordenação do vetor A = {2, 5, 32, 21, 102, 1, 11, 24,
35, 44, 56}. Informe a quantidade de comparações e trocas
efetuadas.
4. No método de ordenação por inserção, a cada passo, o menor
elemento é procurado para que seja inserido na sequência já
ordenada. Essa pesquisa pode ser sequencial ou por busca binária.
Apresente um exemplo e mostre qual abordagem é mais vantajosa.
Exercícios
5. Implemente um programa que simule o jogo do Bingo. O
programa deve gerar sucessivamente números aleatórios
compreendidos entre 1 e 90 até que o usuário digite o caractere $.
Para facilitar a verificação da cartela vencedora, o programa deve
apresentar a lista ordenada de todos os números já sorteados após
o sorteio de um novo número. Use ordenação por inserção.
6. Escreva um algoritmo para a função ContaDistintos para contar
o número de elementos diferentes existente num vetor ordenado.
7. Escreva um algoritmo que ordena de forma crescente as letras
pela frequência de ocorrência em um texto informado pelo usuário
através do teclado. Utilize um dos métodos de ordenação.
Exercícios
8. A mediana de um conjunto com um número ímpar de elementos é o
valor central que se obtém após ordenar o conjunto. A mediana de um
conjunto com um número par de elementos é a média aritmética dos dois
valores centrais que se obtêm após ordenar o conjunto. Por exemplo, para
obter a mediana do conjunto de valores {1, 3, 4, 5, 4, 2}, considera-se o
conjunto ordenado {1, 2, 3, 4, 4, 5}; os dois valores centrais são 3 e 4,
pelo que a mediana é 3.5. Escreva um programa para achar e imprimir a
mediana de um conjunto de valores inteiros introduzidos pelo utilizador,
até um máximo de 100 valores, possivelmente com valores repetidos,
a) usando o método de ordenação quick sort;
b) usando o método de ordenação por inserção;
c) modificando o método de ordenação quick sort, de forma a determinar
a mediana sem chegar a ordenar completamente o vetor. (Sugestão: não
ordenar sub-arrays que não contêm o elemento central.)
Exercícios
9. Considere a execução do algoritmo Quicksort visto em sala (pivô
escolhido no meio do vetor) com o vetor [ 2 10 1 8 20 5 14 13 9 ].
Quantas chamadas do procedimento Partição serão feitas para ordenar
esse vetor? Qual o pivô utilizado em cada uma das chamadas? Quais são
as partições (sub-vetores) resultantes de cada uma dessas chamadas?
10. Considere uma grande empresa com 8000 funcionários, onde a
maioria dos funcionários possui um ramal de telefônico de 4 dígitos. Ex.
4735 – Luiz, 6833 – Marcos, etc. Proponha uma estrutura de dados e um
algoritmo que seja eficiente tanto para inserção de novos ramais quanto
para fazer uma pesquisa pelo funcionário usando o ramal como chave.
11. Dada a sequência de números: 3 4 9 2 5 8 2 1 7 4 6 2 9 8 5 1,
ordene-a em ordem não decrescente segundo os algoritmos MergeSort e
QuickSort.
Exercícios
12. Um amigo lhe diz que é capaz de ordenar qualquer conjunto de
6 números com no máximo 8 comparações. O seu amigo está
falando a verdade ou mentindo? Justifique.