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

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. 
[Solução baseada em pesquisa exploratória – sua tarefa! :) Envie-me a resolução e enviarei
um feedback]
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.
Por exemplo, 1 2 3
 B B A
• Encontre o menor elemento: 3
• troque com 1: A B B (3 2 1)
• estabilidade violada: entre B B (2 1).
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;
1
 ANÁLISE DE ALGORITMOS
Bacharelado em Ciência da Computação
   }
}
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.
O número mínimo de comparações e movimentos ocorre quando os itens estão originalmente em
ordem e o número máximo ocorre quando os itens estão originalmente na ordem reversa, o que
indica um comportamento natural para o algoritmo. Para entradas já ordenadas, o algoritmo
descobre a um custo O(n) que cada item está em seu lugar. Logo, o método da inserção deve ser
utilizado quando o arquivo está “quase” ordenado. Portanto, tem-se:
Melhor caso: (n)
Caso médio: (n2) 
Pior caso: O(n2)
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}. 
[Solução livre, pois você pode considerar Heap máxima ou mínima… tarefa sua! :) Envie-
me a resolução e enviarei um feedback]
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.
Verdadeira, afinal o RadixSort tem complexidade (d(complexidade do algoritmo de
ordenação estável aplicado)), onde d é o número de dígitos.
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? 
Cada chave poderia ser substituída por um registro contendo dois campos: a chave antiga e
2
 ANÁLISE DE ALGORITMOS
Bacharelado em Ciência da Computação
um número inteiro com o valor da posição de cada elemento no veto original. A função de
ordenação continua comparando as chaves originais e no caso de chaves iguais, usa-se o
campo adicional para determinar a ordem entre os elementos.
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”. 
Análises experimentais têm mostrado que se a sequência de entrada couber inteiramente na
memória principal, então, as versões in-place do QuickSort e HeapSort executam mais
rápido que o MergeSort. Para as aplicações em tempo real em que se tem de apresentar
garantias sobre o tempo necessário para completar uma operação de ordenação, o QuickSort
não é uma escolha adequada em função de sua complexidade para o pior caso.
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.
Basta alterar o método do particionamento do QuickSort para considerar zero como o pivô.
Após a partição, deve-se realizar uma nova passada pelo vetor para garantir que os zeros
fiquem entre os números negativos e os positivos. Na nova passada, os elementos vizinhos
ao ponto de partição serão trocados pelos zeros encontrados de cada lado do vetor.
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.
[sua tarefa! :) Envie-me a resolução e enviarei um feedback. É imprescindível entender
como cada um dos algoritmos estudados funciona e o porquê de sua complexidade
computacional]
3
	Lista de Exercícios de Fixação 02