Exercicios de Fixação 02 - Análise de Algoritmos de Ordenação

Prévia do material em texto

ANÁLISE DE ALGORITMOS
Bacharelado em Ciência da Computação
Lista de Exercícios de Fixação 02
Análise de Algoritmos de Ordenação
1. Compare os algoritmos de ordenação estudados considerando os seguintes critérios:
complexidade de tempo (para o pior caso), estabilidade e se in-place ou não. 
2. Elabore um vetor-exemplo para demonstrar que a ordenação por seleção (Selection Sort) é
instável. Mostre os passos da execução do algoritmo até que a estabilidade seja violada.
3. Dado o código-fonte do método de ordenação por inserção, a seguir, efetue a análise de sua
complexidade assintótica para o melhor, pior e médio casos (descreva também o que
representa cada situação).
void insertion(Item v[], int n){
   int j;
   for(int i = 2; i <= n; i++){
      Item x = v[i]; 
 j = i – 1;
 v[0] = x; 
   while(x.compara[v[j] < 0){
v[j+1] = v[j];
j­­;
 }
 v[j+1] = x;
   }
}
Observações: A implementação foi efetuada para um conjunto de n itens sob a forma de um vetor
do tipo Item (genérico). O método compara realiza a comparação entre 2 valores a e b, retornando
um valor menor que zero se a < b, um valor maior que zero se a > b e um valor igual a zero se a = b.
1
 ANÁLISE DE ALGORITMOS
Bacharelado em Ciência da Computação
4. Exiba os passos da execução do método de ordenação Heap para o seguinte arranjo de
dados: {2, 5, 16, 10, 23, 39, 18}. 
5. Se o método estável utilizado pelo Radix Sort for o Merge Sorte, sendo assim, a
complexidade assintótica do Radix Sort seria (nlgn), considerando d constante. E, se
comparado ao Merge Sort, o Radix Sort é mais vantajoso quando d < lgn, ou seja, quando o
número de dígitos for menor que lgn. A afirmação é verdadeira ou falsa? Justifique.
6. QuickSort não é um algoritmo estável. Que tipo de transformação você poderia fazer nas
chaves (elementos) para que ele se torne um algoritmo estável? 
7. Comente a afirmação: “O QuickSort é uma escolha excelente como algoritmo de ordenação
para finalidades genéricas no uso em memória. Entretanto, sua performance temporal O(n2)
para o pior caso faz dele uma escolha pobre para aplicações de tempo real”. 
8. Dado um vetor contendo números inteiros, deseja-se reorganizar os elementos dentro deste
de forma que todos os números negativos precedam os não-negativos. Indique como um dos
algoritmos de ordenação, estudados em sala de aula, deve ser alterado para conseguir tal
organização em tempo proporcional ao número de elementos do vetor. Estenda sua solução
para garantir que haja zero(s) entre os números negativos e os positivos.
9. Com base nos algoritmos estudados e implementações disponíveis via SIGAA, apresente o
passo-a-passo para a ordenação do vetor v = {3, 1, 2, 7, 5, 2, 6}, para cada um dos
algoritmos de ordenação estudados.
2
	Lista de Exercícios de Fixação 02