Algoritmos e Estrutura de Dados I - AE22CP - 2012/2
Bruno César Ribas

Exercícios

  1. O que é Algoritmo?

Merge

  1. Implemente o algoritmo da Intercalação (merge)

  2. Implemente o algoritmo MergeSort

  3. Considere a função mergesort feita em sala. Que acontece se trocarmos "(p+r)/2" por "(p+r-1)/2"? Que acontece se trocarmos "(p+r)/2" por "(p+r+1)/2"?

  4. Submeta à função mergesort um vetor indexado por 1..4. Teremos a seguinte sequência de invocações da função (observe a indentação): 
      mergesort( 1,5,v)
         mergesort( 1,3,v)
             mergesort( 1,2,v)
             mergesort( 2,3,v)
         mergesort( 3,5,v)
             mergesort( 3,4,v)
             mergesort( 4,5,v)
    Repita o exercício com um vetor indexado por 1..5.

  5. A função mergesort é estável?

  6. Escreva uma versão recursiva do algoritmo Mergesort que rearranje um vetor dado v[p..r-1] em ordem decrescente. Sua versão deve ser integrada com o código da intercalação, ou seja, deve incluir o código de intercalação. A intercalação deve começar com v[p..q-1] e v[q..r-1] decrescentes e terminar com v[p..r-1] decrescente.

    + Escreva uma versão do algoritmo Mergesort que rearranje uma lista encadeada em ordem crescente. Sua função não deve alocar novas células na memória. Faça duas versões: uma recursiva e uma iterativa.

QuickSort

  1. Escreva o algoritmo da separação

  2. Escreva uma função que rearranje um vetor v[p..r] de inteiros de modo que tenhamos v[p..j-1] <= 0 e v[j..r] > 0 para algum j em p..r+1. Faz sentido exigir que j esteja em p..r? Procure fazer uma função rápida que não use vetor auxiliar. Repita o exercício depois de trocar "v[j..r] > 0" por "v[j..r] >= 0". Faz sentido exigir que v[j] seja 0?

  3. Um vetor v[p..r] está arrumado se existe j em p..r tal que v[p..j-1] <= v[j] < v[j+1..r] . Escreva um algoritmo que decida se v[p..r] está arrumado. Em caso afirmativo, o seu algoritmo deve devolver o valor de j.

  4. Um programador inexperiente afirma que a seguinte implementação da função de separação rearranja o vetor v[p..r], com p < r, e devolve um índice j em p..r-1 tal que v[p..j] <= v[j+1..r]. 
      int sep( int v[], int p, int r) {
     int q, i, j, t;
     i = p; q = (p + r) / 2; j = r;
     do {
        while (v[i] < v[q]) ++i;
        while (v[j] > v[q]) --j;
        if (i <= j) {
           t = v[i], v[i] = v[j], v[j] = t;
           ++i, --j;
        }
     } while (i <= j);
     return i;
  }

    Mostre um exemplo onde essa função não dá o resultado esperado. E se trocarmos "return i" por "return i-1"? É possível fazer algumas poucas correções de modo que a função dê o resultado esperado?

  5. Qual o resultado da função separa quando os elementos de v[p..r] são todos iguais? E quando v[p..r] é crescente? E quando v[p..r] é decrescente? E quando cada elemento de v[p..r] tem um de dois valores possíveis?

  6. A função separa produz um rearranjo estável do vetor, ou seja, preserva a ordem relativa de elementos de mesmo valor?

  7. Escreva uma versão recursiva da função separa.

  8. Suponha dada uma lista encadeada que armazena números inteiros. Cada célula da lista tem a estrutura abaixo. 
         struct celula {
        int            chave;
        struct celula *prox;
     };
    Escreva uma função que transforme a lista em duas: a primeira contendo as células cuja chave é par e a segunda aquelas cuja chave é ímpar.

  9. Implemente o QuickSort

  10. Que acontece se trocarmos "p < r" por "p != r" na linha 2 do quicksort (implementado em sala)?

  11. Submeta o vetor 77 55 33 99 indexado por 1..4 à função quicksort. Teremos a seguinte sequência de invocações da função (observe a indentação): 
         quicksort( v,1,4)
         quicksort( v,1,2)
             quicksort( v,1,0)
             quicksort( v,2,2)
         quicksort( v,4,4)
    Repita o exercício com o vetor 55 44 22 11 66 33 indexado por 1..6.

  12. A função quicksort produz uma ordenação estável do vetor?

  13. Suponha dada uma implementação da função separa que funciona assim: rearranja v[p..r] e devolve um índice j tal que v[p..j] <= v[j+1..r]. Escreva uma versão do algoritmo Quicksort que use essa implementação do separa. Que restrições devem ser impostas sobre j?

  14. Escreva uma versão não recursiva do algoritmo Quicksort. sol