ime_2/Exercícios/10 - Ordenação: Algoritmos elementares/Exercícios.md

Ordenação: algoritmos elementares

Resolução dos exercícios propostos

Exercícios 1

1. Vide arquivo isSorted.c nesta pasta.

2. O algoritmo proposto, descrito abaixo, é adequado a verificação da ordenação crescente.

int verifica (int v[], int n) {
   if (n > 1) 
      for (int i = 1; i < n; i++) 
         if (v[i-1] > v[i]) return 0; 
   return 1; }

• Caso base: um ou nenhum elemento. Um arranjo nestas condições está trivialmente ordenado em ordem crescente, não há necessidade que comparações de valores sejam feitas. O algoritmo verifica se este é o caso na linha 2 e, este sendo, pula as comparações e retorna verdadeiro (1) na linha 5.

• Para n > 1: A repetição descrita na linha 3 faz com que na linha três cada valor do arranjo do segundo ao último seja comparado ao seu antecessor imediato, interrompendo a verificação e retornando falso (0) assim que um antecessor de maior valor é encontrado. Doutra forma o algoritmo procede e retorna verdadeiro na linha 5.

3. O algoritmo proposto, descrito abaixo, é inadequado a verificação da ordenação crescente.

int verifica (int v[], int n) {
   int sim;
   for (int i = 1; i < n; i++) 
      if (v[i-1] <= v[i]) sim = 1;
      else {
         sim = 0;
         break; }
   return sim; }

No caso base n >= 1, o que faz com que a repetição com a verificação nunca ocorra. Ora, mas apenas pela verificação a variável sim é designada um valor (1) verdadeiro ou (0) falso. Assim, ao executar este algoritmo com um arranjo trivialmente ordenado o seu resultado é imprevisível: ele retornará qualquer valor que esteja armazenado na posição de memória alocada para armazenar o valor da variável sim. 4. Vide arquivo Sorts.c na pasta da disciplina de Análise de Algoritmos e Estruturas de Dados I.

5. Vide arquivo isSorted.c nesta pasta.

Exercícios 2

1. Vide arquivo sorts.c na pasta da disciplina de Análise de Algoritmos e Estruturas de Dados I.

2. Continua, entretanto a função perderá sua propriedade de estabilidade, isso é, os valores iguais não aparecerão na mesma ordem quem que foram inseridos (estes figurarão em ordem reversa). Para ordenar valores inteiros isso não é de maior consequência senão por mais algumas comparações desnecessárias, mas quando estes valores são chaves para a ordenação de estruturas de dados, isso pode ser indesejável.

3.

a) Esta modificação não alterará o resultado, apenas adicionará uma repetição do loop descrito na linha 3 onde o valor em v[j] é copiado à x e em seguida sobrescrito à v[j], pois nestas condições i + 1 = j.

b) Esta modificação comprometerá a funcionalidade do algoritmo. Fazendo com que o valor em v[j] seja armazenado uma posição antes do que deveria, possivelmente extrapolando o limite inferior do arranjo.

4. As consequências para a alteração

6,7c5
<    v[i+1] = x;
< }
---
 >       v[i] = x; } }
\ No newline at end of file
 >   

São discutidas no item b) do exercício anterior.

5. Esta versão não alterará o resultado final do algoritmo, mas realizará um número maior de atribuições para alcançá-lo, o que prejudica seu desempenho.

6. Sim, a única diferença deste modelo com o algoritmo anteriormente descrito é o uso de um loop while em vez de um for. Assim, o invés de constar em uma única linha, temos que o contador é inicializado na linha 3, a condição de repetição na linha 4 e a incrementação do contador se dá na linha 6.

7. Vide o arquivo backwards_insertion_sort.c

8. Mas, isso pressupõe um vetor já ordenado. O resultado de se realizar esta operação terminaria por manter o vetor embaralhado.

9. O pior caso corresponde a qualquer instância em que os valores do vetor encontram-se ordenados em ordem decrescente. Assim, para um vetor de tamanho n as comparações feitas ao final encontram-se em progressão aritmética:

1 + 2 + \dots + n - 1 = \dfrac{(n - 1)(n - 1 + 1)}2 = \dfrac{n^2 - n}2 \equiv O(n^2) 

10. O melhor caso é aquele em que os valores já encontram-se em ordem crescente. Assimpara um vetor de tamanho n cada valor desde o segundo ao último é comparado com seu antecessor uma única vez, um total de n - 1 \equiv O(n) comparações realizadas .

11. No pior caso, todas as comparações levam à movimentação de dados, portanto, são \frac{n^2 - n}2 movimentações no total. No melhor caso, também. Neste os dados são copiados a uma variável temporária e em seguida sobrescritos sobre a posição donde advieram, totalizando n - 1 movimentações.

12. Vide o arquivo backwards_insertion_sort.c.

13.

14. Vide o arquivo descrescent_insertion_sort.c

Exercícios 3

1. Vide arquivo sorts.c na pasta da disciplina de Análise de Algoritmos e Estruturas de Dados I.

2.

a) O primeiro elemento da lista não é ordenado.

b) Acrescenta-se uma repetição desnecessária, já que não à outro elemento com que comparar com o elemento final do vetor.

3. Sim, está correta, mas o algoritmo perde sua estabilidade. Elementos de mesmo valor são ordenados na ordem reversa daquela em que figuraram originalmente no vetor.

4, 5 e 6. Em ambos o melhor e o pior caso, o mesmo número de comparações são feitas, \frac{n^2 - n}2 o que diferencia estes dois casos é o número de movimentações feitas: respectivamente, n - 1 (os dados são copiados a uma variável temporária e em seguida sobrescritos sobre a posição donde advieram) e \frac{n^2 - n}2 (o último elemento vai para a primeira posição, o penúltimo a segunda, e assim por diante).

7. Vide o arquivo descrescent_selection_sort.c

Exercícios 4

1. Vide o arquivo string_insertion_sort.c 2. Vide o arquivo string_radix_sort.c 3 e 4. Vide o arquivo data_sort.c