COMPUTAÇÃO

Universidade Estadual da Paraíba
Centro de Ciência e Tecnologia
Departamento de Matemática, Estatística e Computação
Curso de Bacharelado em Computação
Professor: Fábio Luiz Leite Jr
Aluno (a):

Lista de exercícios de revisão
1. Escreva um programa que recebendo um vector de números naturais, os ordene por ordem decrescente tendo como critério o número de ocorrências de cada um no vector. Utilize o seguinte protótipo: void ordenaOcorrencias(int v[], int tamanho);
Exemplo:
Input: 1 5 5 5 3 3 2 5 1 3 1 1 5
Output: 5 5 5 5 5 1 1 1 1 3 3 3 2

2. Implemente o algoritmo QuickSort em que o método de escolha do pivô seja através de uma busca aleatória no Vetor que está sendo ordenado.
3. Faça um teste de mesa com o método de ordenação merge sort e quick sort, respectivamente, utilizando as seguintes sequências de dados de entrada: 


S1 = 2; 4; 6; 8; 10; 12; 1; 3; 5; 7; 9; 11
S2 = 8; 9; 7; 9; 3; 2; 3; 8; 4; 6

4. Escreva uma função que verifique se um vetor v[0..n-1] está em ordem crescente. 5. No método InsertionSort, a cada passo, o menor elemento é procurado para que seja inserido na seqüência já ordenada. Essa procura pode ser realizada sequencialmente ou por busca binária. Analise o desempenho de ambas as abordagens, implementando as duas abordagens e comparando.
6. Escreva uma função que coloque em ordem lexicográfica um vetor de strings. Use o selection sort.
7. Explique como os algoritmos de ordenação em tempo linear conseguem ser mais eficientes que os algoritmos de ordenação em tempo linear.
8. Explique por que o radix sort e o bucket sort podem se tornar tão lentos quanto o insertion sort.

9. Como ficaria o algoritmo de ordenação counting sort caso fosse solicitado para ordenar os números em ordem decrescente?
10. Qual é a principal desvantagem do algoritmo counting sort?
11. Discuta como a escolha do pivô pode influenciar no desempenho do método quicksort. Proponha estratégias para a escolha do pivô, visando